We have multiple sites on a VPS, all sites but one send out emails fine. Some users get email notifications perfectly fine while others don't receive anything, not in spam folder either. I was having this issue myself until I switched my email from my normal one to my gmail. Weird thing is when I did that I actually received a email from the site on the addy that wasn't working and my gmail.
Well, you want to search it for the email that failed to be sent (so using a unique email is useful). It should have a unique identifier listed for the email and you can then search that ID to follow through with all the information about that email. You may want to compare with a successfully sent email to compare. If the email appears to be sent successfully, it could be an issue on the receiving side or it could simply be that it's routing somewhere you don't expect (like delivering it locally instead of via SMTP).
I too was having both e-mail and spam issues with XF after installation. I haven't really had problems using the default PHP mail function on my server before using other scripts, but for some reason it won't work well with XF (probably because XF handles it appropriately).
Anyways, not sure if it has already been recommended, but I setup a couple of my domains to use the Amazon Simple Email Service (SES) and everything delivers NICE and smoothly This is a good alternative for small to medium sized sites... however, if you deliver more than 10,000 e-mails a day, the fee really isn't that much!
Any updates on this ? Sorry to jump into this thread but have had one client ask why emails are not getting sent / not landing in members inbox / spam folders... I am assuming it's more server related than a XF issue ? but if i could provide some assistance to my client who has just converted from VB to XF with 50k+ Members (4,475,538 posts) and needs to send a confirmation email / info regarding the switch.. he is stressing about it badly but as ive not delt with this issue or have even touched on XF and emails.. What's the best way to handle this ? Possible just rent a premium service for the initial email send and search for the problem later ?