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?