The vast majority of websites that are inadvertently serving malware have been compromised through the website itself, which can happen totally independently of the web server software or the host.

About the best the host can do is have a reasonable IP blacklist, but even that doesn't stop nearly enough attackers. (My little mail server, hosting only around a dozen accounts, is currently averaging 14 new SSH bans per day for example.)

The only thing that a "secure" host guarantees is that a compromised website can not lead to a compromised server; attempting to measure that by checking the number of malware-hosting websites at a service provider is the wrong way to go about it.

All that said, if you want a "secure" host without spending a lot of money, your best compromise would be an OpenBSD VPS, and then either spend a lot of time learning how to set it up correctly (and maintain it), or have someone do it for you.

Having NetSol and GoDaddy on a list of potentially "secure" hosts is hilarious.

edit: I'd recommend checking the Sucuri Blog (http://blog.sucuri.net/) for an idea of who's been compromised and how they've responded. Sucuri's pretty good at keeping track of all this stuff.

Blacklisting alone don't tell if a hosting company is secure or not, but is a good indicator of how it is being perceived from the outside.