Twitter Rate Limiting for Rest API over 3G for Mobile

Question

Twitter have a 150 requests per hour limit for their unauthenticated REST API, I am displaying 2 of the latest tweets in my iPhone application and I don't want to authenticate any users, the problem arises when I fetch tweets over 3G when I get a "Rate limit exceeded" error, what are my options ?

I understand that Twitter calculates this limit based on the public IP of the device, which for mobiles can be shared with many other devices, causing this problem.

If you check out Adele's new iPhone app, it has a news section that pulls in tweets, while my app showed rate exceeded, this list updated. The only idea I have is they are fetching these results on the backend, saving the results or caching them and serving them through their server rather then querying Twitter directly from the application.