Ok, thanks everybody. The option to host the list in one server and use pair or futurequest seems interesting. I also like the fact that vservers is something in between a host and a dedicated server. I contacted several hosts and hopefully that'll help me decide.
Just to make this thread useful for other people:
About pair: I've used pair for almost two years and the service is good. The only problem is that support (only email. TO me, living in argentina, phone suppport is not an option, even if they had) is very slow and not very helpful. However they take very good care of their servers and the information on their site and good server setup (IMO) helps solving most problems without calling support.
I have read many forums on this topic and never saw something bad about FutureQuest so they must be really good.
And both have mailing list support. My particular problem (and a possible problem for the minority here with non-english websites) is that they require mail confirmation and you can not edit this message. So if a users subscribes to my list from a form in my site, he or she receives a cryptic (bacause it's in english) confirmation mail that they have to reply in order to subscribe....
