I had tables with over 500,000 records but because I normalized my tables and carefully chose my indexes, I never saw more than a one-second delay in single-record searches. When I was choosing all records matching a particular indexed field, that was pretty fast, too. As noted by the others, indexing and careful structuring will let a 50,000 entry table fly on most modern systems.
There IS a caveat... Using Windows XP or higher, you would do better to not memory-choke your system. If you have a PC with 8 GB of RAM, the worst-case simple scenario of having a big front-end file and a big back-end file still won't cramp your style. Doing really big (1.5-2.0 GB) back-end files on a 4 GB system might rarely force you to start page-faulting, which would be a performance hit. But if your system is not memory starved, you'll never care about size as long as you don't max out Access itself.