It's also worth noting that, because they control the storage for your hosted server, they can access it without your permission whether you want to allow them to or not. Just reset the ssh keys and bounce it ("oops, power failure!"), or just read out the data from your logs via a snapshot of the partitions, etc..Definitely, which is why, as others have pointed out, you have to get a host you can trust.
Still, storing recoverable passwords (which is what most people mean when they say "cleartext") without clear notice is a terrible idea for all the reasons people expect. The list can be stolen or misused, and this sort of thing happens routinely.
Whilst I agree that storing cleartext passwords is not a great idea, I think the worse idea is to rely on every single web service you belong to to keep your authentication/authorisation credentials secure.
Your process of keeping your credentials secure should not depend on the security practices at any single one of the services you use.
People who publicly criticise hosts for storing passwords in clear, but then use the same password for multiple services, are nothing less than hypocrites. Remove the log from your own eye before picking at the straw in someone else's.