Ia recomendar olhar no lowendbox.com, mas se precisa ser no BR, conheço duas que ja usei: Host1Plus e AdentroCloud
Gostei do AdentroCloud, mas os preços... realmente salgados hahah, inviável 
Ainda bem que contou sua experiência com a Host1Plus, assim nem perco meu tempo com eles... já tive com a Locaweb e não quero de novo!
Alguém sabe se a UOL Host funciona bem, atendimento bom?
Acho que são ainda mais caros. Mas nunca fui cliente deles. A Microsoft tem servidores no brasil também, mas acho que vai ser igual a amazon aws: caro e dificil de usar (ip externo diferente do interno, etc...).