Yo también te recomiendo que utilices varios buscadores de hosting:
http://www.buscahost.com (español)
http://www.buscahosting.com (español)
http://www.buscandohost.com (español)
http://www.paginasdehosting.com/ (español)
http://www.hostsearch.com (inglés)
http://www.tophosts.com (inglés)
Y una vez que tengas unas cuantas empresas candidatas hagas búsquedas sobre ellas en este foro o preguntes por ellas.
Sobre el registro de dominios, godaddy.com es una excelente opción, y barato...
