Well yes and no, not all users were receiving e-mails from us. While we are using a static IP address most ISP's don't like getting e-mail from an IP address that does not map back to the domain of the e-mail sender (reverse DNS is the term). Checking the RDNS is used as a spam fighting measure by many ISP's and because of this many of our users will not get e-mails from this site.
BUT.... but.... I believe I have just fixed this. I moved the site over to a Windows XP based machine and I was able to add a utility that takes the SendMail Perl script built into the site and forwards it to my Gmail SMTP account for delivery. Joe helped me test to his work which was previously blocking e-mails from this site and now completes.
Now I think I have it fixed.