While some shared hosting may offer multiple IPs you can bet that they are probably already beaten down and next to useless for most things, especially on the larger webhosts like Hostgator. Also chances are that if you cannot see a place to allocate multiple IPs in your control panel, you are pretty much stuck with the same IP.
I am not familiar with Cloakfish, but there is no such thing as "unlimited" IP addresses. IPv4 only allows for 4.2 billion addresses and those are getting allocated quickly.
Personally I don't trust paid proxies, but that's just me. I know there are some good ones out there, but I would rather have complete control over my endpoints. That way I don't have to worry about who is snooping in on my traffic, etc.
You can go to someone like Spry and get a VPS with two IPs and a terabyte of transfer for around $33/month. For an additional $50/month you can get an additional 25 IPs that are all yours - no sharing. If one of them gets banned, it's because of something you did and not one of the 10,000 other people using the IP like with shared hosting. You can rDNS them too, and they are pretty well scattered across the address space so you don't wind up with fishy looking sequential IPs.
That's a total of 27 private IPs for $83/month, which for some is too expensive but depending on what you're doing it can be very cheap.
Oh and there are plenty of legitimate reasons why someone would need multiple IPs, particularly when doing load testing and security auditing of web applications.
[Disclosure: I am not associated with Spry, but I have been a VPS and dedicated server customer of theirs for some time and have been exceptionally happy with them.]