It worked fine on my server when I tested it, so it is something being blocked by your outgoing servers. It appears to be an issue on your hosting provider when using a Reply_To address with yahoo. I don't feel it is far reaching based on my investigation, but I don't really know the full cause either.
I updated the webassist/email/mail_php.php file and uploaded a new webassist/phpmailer/ folder to the server that it now uses.
I probably left my email address in the to field and your BCC was set to the mail-tester site, so I removed it. You should be able to open the interface and make changes, but save a backup of the mail_php.php file. It will likely be overwritten and should not be re-uploaded. The backup can be used if you accidentally overwrite it.
The mail tester I sent you to is pretty reputable and commonly used. I've worked through the issues listed on it and gotten them fixed for customers in the past. Your hosting provider blowing them off seems inaccurate to me, as does their assessment that the previous issue was with our code without any data pointing to what the exact problem was. It was akin to "I don't know what the problem is, so it must be someone else", which isn't really helpful or scientific.
The fact that our email code worked with other email addresses and only failed with yahoo, hotmail, and aol really does imply that the code syntax is fine and that the outgoing email server was blocking the sending for some reason. If we had direct access to your SMTP email logs we might be able to see the true reason, but it appears your hosting company's support didn't go that far for you.
The good news is that the new email library does seem to send, so there was something about our email library that was contributing to the problem, however that same library works on a lot of servers, so your hosting provider is a factor of some sort as well. I don't feel compelled to warn others about this issue since I'm not confident it is an issue for others.
I also can't comment on how long the issue has occurred or where else. It appears it would only be an issue on contact forms since that would be the only time a FROM and REPLY_TO wouldn't match.