it is only a problem with Mobile Me and iCloud addresses? other addresses work if you include the from display name?
that is strange, the from display name is normally only a problem that the SMTP Server may experience, for example.
the code you reference:
$MailFrom = "FromNameHere|WAfirstname.lastname@example.org";
adds the from header as:
From: FromNameHere <email@example.com>
Some servers don't like that format though, mostly it's an exchange issue but other server will have a problem too.