obviously the users would have to be logged in for this to work, which in your case might not be the desired use. Still, this could be an optimization step that could save you some cash down the road.
you don't need more vms to get around their rate limit, you just need to query their api using a clientside language like javascript, that way the ip twitter gets is the ip of the user, not your servers. The company I work at has awesome search, so I have a tool which grabs tweets from individual user's streams (if a customer has an issue with my product and tweets about it I like to search their public twitter stream to see if they've mentioned us or our competitors lately). My script is a python one using httplib, but I realized that I could just as easily make these queries using jquery and send them anywhere I like. This moves the rate limit from your server's ip to the user's ip. If a bunch of people are using your product from the same office it could be a bit of an issue but you could probably detect that (with their 420 chill out code) and use one of your vms ips until that office's ip cools off again. That'd probably make your overhead quite a bit cheaper I'd imagine.