ASP.Net Search returning inconsistent results

I've built a search page with asp.net (C# code-behind, SQL Server 2005 DB). The form let's you put in any of first name, last name, ssn's, etc. It returns results from the database from different tables. I have never had any problems with the performance of the search. I do have one user that reports inconsistent results. They will put in a SSN and get the results back, say 15 records match the search criteria. The next time they perform the same search they get 0 records. Then they can log off and come back later and perform the same search and get 15 records again. I have been unable to find a pattern or figure it out. The person sits on the same network but in a different location. I'm using membership to handle accounts and logins, but this person has all of the permissions required to do the searches. It's a standard asp.net page with text box controls for criteria input. Is there something I could be missing regarding what I need to be looking for? Any suggestions on tracking this down would be greatly appreciated.