para utilizar magento en cualquier proveedor de hosting puedes tenerlo solo que cualquier proveedor te recomendara utilizes un servidor dedicado ya cuando muy fregado un vps ya que magendo por el tipo de CMS suele consumir demaciados recursos y ellos prefieren lanzarte de entrada a un paquete grande donde tienen mas confianza no dara problemas... y aclaro suele hacerlo mas no es una regla, por lo que quizas puedas comensar en un vps sin problemas.
prueba con
http://www.hostgator.com/apps/magento-hosting.shtml
con
http://www.1and1.com
o hasta en la pagina de magento encontraras recomendaciones de hosting afiliados que ellos te recomiendan
http://www.magentocommerce.com
y lo que ha hecho el usuario xento si califica como publicidad y autopromocion ya que de 6 mensajes que publico en el foro 5 fueron para hacer promocion a ese proveedor, y hacerlo por privado no lo exonera.