you won't have a problem. once you hit 5000 or so hosts you might have to multithread or follow some other solution.
a number of large organizations use nagios. it's hard to get scalability numbers because the number of hosts vs the number of service checks you have can have varied performance, and how often your service checks are running, and whether host checking is turned on, etc etc .
to give you an idea, we've got ~200 hosts and ~4500 passive service checks running at 1 min and 5 min intervals being received from various distributed nagios sites to a dualcore p4 3ghz, and its load averages ~0.25. This is nagios 2
I've heard of comparable hardware with a few more cores doing ~4000 hosts though.
if you have the option, set up your checks as services rather than defining 2500 hosts, and nagios will have absolutely no problem. You'll be fine anyways though.