If you were to use azure table storage and use shared access tokens for authorizing access to query results, you could run the whole thing from any individual data center for under $500/month.

Assumption is that every IP (all 4.3 billion) had about 100 bytes of data stored about them. That is ~430gb of storage runs you $30/month. The 10 billion queries to that storage costs about $360/month. ($.0036 per 100,000 transactions)