I've got email forwarding set up for a domain on 1&1.co.uk and don't have any problems on gmail. Others who have mail forwarded from the domain don't have any problems on hotmail or yahoo either.

Maybe Google gives extra trust to 1&1; or maybe there is some other thing that they check for.