Depends largely on the hardware and how one architects the Exchange design. Also depends on how much traffic there is to/from each mailbox.
I've worked with an Exchange 2000 active/passive cluster server that had over 10,000 mailboxes on it, but the vast majority of those were light help desk users and it rarely had more than 5000 users logged on at any one time. I've seen plenty of single servers that had over 1000 mailboxes on them.
Perhaps if you could narrow it down with some budgetary constraints or give an idea of what your end goals are folks would be able to give you some more firm ideas.
Good luck!
Gary McDonnell