Follow up w/ the Centralize No-call List project, I did a little benchmark on phone lookup using python, running on my wimpy old Thinkpad X40.
It takes a little under 0.08s to perform a search for a single item in 988,889 items, around 10% of all the mobile phone numbers in Hong Kong as of June 2007, i.e. around 12 requests per second. On a decent server (i.e. any of the modern dual core Intel or AMD) w/ decent amount of RAM the capacity should be a lot higher.
Update (24/9): I set up PostgreSQL for win32, stored the same dummy no-call list in it, and wrote a script to query PostgreSQL. I am surprised that this is an order faster than in-memory search! More tests later.