Hi all,
Thanks for the extra info @chefchiller. This worked at my site, perhaps it will work for you as well?
For all strato users:
1. Login at strato
2. Security -> Spam settings for guestbook
3. Turn off all filters
Once you have done this the issue is gone! At least at my site ??