BIG Scalability

I have used this forum before to find good suggestions for VPSs, but now I'm in need of something that I have no idea where to go to to get the solution, or even what that solution may be.

First, my situation is this...

I've built a web application in PHP for an emerging company and it's primary function is to crawl remote websites that we are provided API access to (via lib_curl_multi). The company's clients login to their account and initiate the crawler on a domain of their choice that has API access. They are then added to a queue (to prevent abuse/server overloading) which performs the crawl. The crawl process takes anywhere from 1 minute to an hour and uses anywhere from 50KB of bandwidth to 30MB depending on the remote domain.

The client anticipates their first 3 months needs to be 1,000 crawls every 24 hour period, obviously meaning crawls would have to be done in simultaneous 'groups' to ensure all 1,000 in the queue can be done throughout the day.

That means for their first 3 months, they need bandwidth of about 10-15GB per day and I have NO CLUE what kind of hardware setup they'll need.

That's not really the issue though as I'm sure most dedicated server setups found here can support that. The problem is that after that 3 months they anticipate a ten-fold increase (obviously this would be a gradual build-up) in the number of crawls needed to be done daily, meaning 10,000.

Now that's a huge increase in bandwidth as well as CPU and memory needs. What kind of setup and/or host could accomodate this constant need for scaling without charging ridiculous prices?

My theory is there needs to be one dedicated server or VPS to serve up the website and its content, whereas there can be one or many dedicated servers (expand as they grow kind of deal) that process the crawler queue in the background (hopefully geographically dispersed as their clients are worldwide). EDIT: I forgot to mention that if the website server is separate from the others, they MUST share the same MySQL database as that is where the queue is stored.

I hope I didn't confuse anyone. I'm great with programming, but hardware and hosting's not my strong point so please let me know if you need clarification.