Do you have your SQL tables properly indexed by the columns you're checking against? I'm sorry but even with a low powered server 2000 records should be well less than one second ... if you have indexes setup. (I have a small desktop server with 4GB or RAM that checks name, email phone number from 5500 contacts in 300ms, for example)
Post you database creation schema, let's take a look