We calculated that it cost us about 1.20 euro do keep this up per user per month. And mind you these costs were primarily network bound so it doesn't matter if you have faster hardware.
There are some optimization techniques you can do to bring this down (for example use imap push) but with gmail you are looking at about 2K connections per IP, you do the math.
Actually you can do this (and we are doing this through partners) on the cheap but the experience you can provide will not be appealing unless it is an add-on experience on an existing product.
Do you mean that google only allows you 2,000 concurrent IMAP connections per client IP address, so you need to scale up your requesting IP pool along with your user count?