Users not receiving emails (seems to be a wider issue)

Hi. I have a WP on all my client domains. Users who register on these WP sites that are gmail, hotmail, aol, etc are not receiving any kind of notifications.

New registrations do not get the confirm link or are not notified of new posts. If a user is not one of the forementioned, they get all the notifications. Why is this?

I have looked all over for this wider issue and there seems to be no resolution but to contact your host.

I have also sent test emails direct to these gmail, hotmail, aol, etc accounts using the pop accounts from these domains and they receive them but when its done via WP, it never works. I have used the native WP mail system and this does not resolve and i have also used the WP Mail SMTP and the same. The issue from what i can see comes from the WP setup cos i have tested all angles. I have a lot of clients who use WP and it will be dissapointing to have to tell them to ditch WP.

Please help.