Yo también me decantaría por el WebService.
Por cierto, el siguiente código es para conectarte remotamente a una BD Access. No sé si funciona y si será posible con tu Host, pero por intentarlo...Es para VB6, pero bueno la connection string te sirve:
http://www.vbforums.com/showthread.p...96#post2223896
Ya nos dirás si te funciona.
saludos!