1. Can you modify your system to return results based on a subset of their followers? If this is still of value to the user, it looks like the way to go, providing results based on a subset followed by another set of "final" results based on the full follower graph.
2. If you have enough celebrity-scale accounts using your service, are you able to share their followers details and cut down on time used to pull them?
3. On the business side, the service sounds dangerously like something that would be killed by Twitter if it becomes successful, by some definition of successful because you are pulling out their follower graphs. Look at Tumblr and Instagram. While it is good to milk it while you can and build it with ambition, it is also wise to look further and prepare for the day if it gets shut down and revenue goes to 0. If you have nothing to lose, go ahead, but be aware.