sql seacrh query performacne for large data

Question

 

I have a customer deposit WINDOWS application which has the UI which allows the user to search for a particular customer by his Name,cust_ID,status and company. The customer table is an sql table that has more than 15000 records. In each page of search window Im displaying around 20 records.

Since there are large number of records, I have created a view by name "seacrh_customer_vw" from which im fetching the records onto my UI. Since there is huge data,even seacrh for some cutomer that belongs to a company takes more time.

So when ever I query the database i use   da.fill (dt,lowercount,uppercount,"datasetname")   so that the query will yield only 500 records at a time. initially lowecount=0 and uppercount=500 ,so initially when page loads i get 0 to 500 records. SO when teh customer reaches the last page that has 500th reocrds, again it will hit the database and executes the same query and this time it fetches the records from500 to 1000 with lowercount as 500 and uppercount as 500......

Here for each 500 records,IT is hgitting the database. Is there any possible approaches to avoid this database hit for every 500 records and makes the seacrh query faster.The customer table will go on frequent updations,hence indexed views may not be a gud option. Is ther any concept of querying the database only one and load the data into datatable whenever needed say 0-500 records for first time and next from 500-1000 records.??..plz help I have to increase the seacrh performance to be less than 3 secs.