Best VDS hosting w/ mail server control?
I'd like to make a web site/domain that allows users to send anonymous e-mails to each other. In other words, their actual e-mails will be stored in a mySQL database, randomized forwarding addresses will be made on the fly, and incoming e-mail will be examined for those addresses and sent to the appropriate person. (The way in which Craigslist handles anonymous e-mails for its classified ads is a good example of what I'm trying to do.)
Although I've gotten a handle on PHP and mySQL, I'm pretty unused to manipulating mail servers. I have a couple of questions:
1. Can you suggest a good hosting solution for the above functionality? I see some companies that offer VDS/VPS with the ability to control the mail server, but I'm not sure if some are more reputable than others.
2. What mail server would you suggest I use, given that I have no experience with any and am trying to learn?
3. Any resources -- books, web sites, forums -- that would help teach me how to use your suggested mail server would be awesome.
Thanks so much for your help!