Whats a good way to determine the number of records to present to a user until he has to switch to a second page?

I always wondered where I should draw the line, ie. how much tabular data a human may visually process until the site becomes a visual mess and the user cannot get any useful information out of the mass of records presented to him.

Historically, the sites and apps I worked with were either too focused (resultsize rarely went over 10) or the only search parameters led to unique results. Now that I actually have a site that could potentially present throusands of records, the question came up again.

Some pages offer customization of the number of search results, ie 25, 50 or 100 per page, an approach which might suit some users, but I find a bit apologetic (the "whatever you want" approach).

Is there some kind of good rule of thumb? I guessed I'd rather ask before just setting the limit anywhere, and either confusing the user with information overload or frustrating him by having to click "next page" too often.

Note: The user does not know what he wants. I talked to them, the answer was technically my question directed back to me.