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.
