The 5,000 document limit is the default limit on documents returned from a full text search. "Add Search" is subject to this limit because it uses an FT search. This limit can be increased or removed by changing a server parameter.
You can set the Notes.ini parameter "FT_Max_Search_Results=n" to change the search limit. Set it to 0 to remove the limit altogether.
An alternative, as pointed out by someone else here, is to do a db.search or view selection to explicitly select documents in your code. If you still want to use agent searches, remember that this does an FT search, so if the database is not already FT Indexed, this will be no faster than doing a database search in LotusScript, and a straight search will let you use any valid selection formula, wherease an ftsearch is pretty limited.