Any ideas about why it affects one German recipient and not another (who presumably uses a different ISP)? If it is, in fact, the result of new EU rules it seems like it should be universal.
Rules are rules. How they are
interpreted and
implemented is something else entirely and each site is responsible for their own interpretation and implementation. Your recipient appears to have chosen a very conservative (strict) interpretation or it may be that AOL's response to the. new EU requirements may have been based on a very loose interpretation. That is common any time new rules or standards are promulgated and it can take some time, even years, to work the kinks out and every provider is fully compatible with everyone else.
(Technology changes so fast that sometimes full compatibility is never achieved because newer technology has made it obsolete.)