Am currently using a VPS server to support my 100k sized email database.
Wanted to find out what sort of server would I need to support a 1 million to 5 million sized email database?
A dedicated Server, or clustered email server server should satisfy your requirement.
To cut costs, I would recommend against a dedicated server. Why not just get multiple VPS servers and just split the content amongst them? Just cluster them.