Sorry it has taken so long for someone to get back to you. The SaaS email filter, while optimized for Microsoft Exchange-based environments, will work in it's basic function with any SMTP filter that will accept mail from a private relay filter.
The problem you may have with services such as Hostgator, Bluehost, etc., is that many of them only provide shared-hosting services using cPanel. These service providers place certain rules in enforcement making our service incompatible, such as hard SPF Filtering (which causes mail relayed by the filter to be denied, as SPF checks by the backend server will ultimately fail).
While I personally haven't tried using the service with either Hostgator or Bluehost, I have tried to get the product to work with a similar shared hosting service operated by Green Geeks, and after much troubleshooting and working with the provider, determined it simply would not be possible. From my own experience with Bluehost, I suspect the result will be much the same.
I would recommend contacting the webhost you plan to work with and ask them if their hosting accounts allow you to turn off SPF Record Checking or other webmail security, and allow you to block SMTP traffic from all but two ranges of IPs. If they do, it should work. If they do not, it likely will not work.
Virtual Private Servers may have more flexibility, but I have not yet personally tested in this regard.
The SaaS Product is one of those services where the ownership and the ability to make high-level changes to the server and/or firewall are important. Some hosted services, such as Google Apps and Office 365 have been tested and found will operate well with the base spam filtering functionality.
Some hosts have proprietary DNS MX and do not allow inbound from a 3rd-party, e.g 1and1.com. However, having worked with both Bluehost and Hostgator (using Postini 10-years), you can use a 3rd-party. Depending on your hosting package, you may need to submit a support case asking for them to add McAgfee as an allowed relay.