How to customize form messages?

Hi people,

I am using Drupal 6 with simplenews and ajax modules.
http://drupal.org/project/simplenews
http://drupal.org/project/ajax

I use the ajax module to power a newsletter subscription form in a block.
I learned to use hook_form_alter to change the text for the form elements.

What I was unable to find out was how to customize the form messages, such as "Email field is required." and "You will receive a confirmation email shortly containing further instructions on how to complete your subscription.". The site has mostly german visitors, so obviously I don't want to present these messages in english.

What I tried:
- I did not find these strings in the translation interface.
- I tried string override module, but it seems to have no effect. (plus, I'm not sure how it deals with tokens)

-----

Aside of this, I also would like to have a template file for the form (to customize the placement of the form elements, not just the block html). I think this was possible somehow with form_alter + a tpl.php file, but I can't find any documentation.

----

Thanks,
donquixote