Lo primero que puedes hacer desde tu ordenador es una consulta de dns , a ver si existe el dominio .
shell# nslookup nombredominio.com
Si tienes windows idem
c:> nslookup nombredominio.com
También hay muchas páginas que te hace el trabajo . Lo que no sé es si se chivan a las compañias de hosting ....
Una de ellas :
http://www.all-nettools.com/toolbox