The result of a search for a non-existing user should not be a 404.
"User not found" or "User unknown" would be more appropriate.
A user is a page and therefore a 404 fits perfectly. A user not found allows to test our database.
From a user perspective I agree with Tom. Entering a user name in the user search should not result in a page that looks like something is broken. As a user I perceive the search like the search in google ;-) And google tells me that it could not find content for my request rather than that pages were not found on the server. We can still send 404 but with a more user-friendly message and without the "its-broken"-looking image.
@ @hotho: Doesn't the current situation allow testing our database as well? A user page that is not found == A user that does not exist?