Buenas,
Pues lo que tienes que hacer, es crear algunos registros MX que apunten a los servidores de Google. En la ayuda de Google está bastante bien explicado:
http://www.google.com/support/a/bin/...s&answer=33352
Tu proveedor de hosting no tiene porqué darte soporte o no. Realmente solo debes de tener acceso a cambiar los registros DNS de tu dominio, y ésto todos los proveedores suelen ofrecerlo.
Lo de cambiar de proveedor, pues solamente debes de desbloquear el dominio (si es un .es no hace falta) irte al nuevo proveedor (puedes preguntar en el foro de hosting por uno bueno) y pedir una transferencia de dominio.
El push con Gmail lo hago mediante un tercero. Como si fuera MobileMe, pero gratuito. Ahora mismo no me acuerdo del nombre y tengo el móvil en el coche, ya te diré mas tarde. Lo uso para calendario y correo electrónico, para contactos no he probado la verdad.
El tema del Outlook ya te digo que no sé si es posible o no, creo que si pero no es nada seguro. Aún así, las funcionalidades de Gmail a mi me gustan mucho más que las de Outlook.
Es cuestión de acostumbrarse.
Y también puedes alojar la web en un sitio y tener el correo funcionando por Google Apps. De hecho, es lo que hace todo el mundo. Y yendo más allá, las páginas con mucho tráfico usan varios servidores (Google me parece que eran 20.000 servidores, casi nada...).
El tema del pago, pues son cero euros. Es un servicio gratuito hasta creo que 50 direcciones de email. Cada una con 7GB de espacio (y está en aumento). Yo Gmail lo uso desde hará algo más de cuatro años y ando por el 9% de esos 7GB.