The maximum is 750 messages with maximum age of 14 days.
I had this problem also some time ago that users want more or older mails.
I wrote a short agent (for selected documents) that sets (as far as i remember) routed time and postet date to actual time, this forces the BES to synch this messages.
John, do you have a link to this new feature with 4.1.5 ? Sounds interesting, would like to read more about it .
Edit: Found it myself :
BlackBerry Search Results
Very interesting ....