Couple things here.
First, in recent versions of 4.x we rely on indexing services in Exchange for keeping the filters up to date for message count and generating the mailstack for voice, fax, receipts,emails that are presented to the caller when they dial in. Unity does not construct that index on the fly when you log in any longer unless for whatever reason it is not up to date when we do (i.e. it's a newly imported mailbox or the indexing service has not gotten to it yet or the like).
When a subscriber is imported into Unity we insert requests for that mailbox's inbox on the Exchange service to keep an index of messages based on type/read status such that when we log in we can quickly get a message count to present and construct a stack of messages in fairly short order. This is far, far faster than doing it on the fly and has helped sites with very large inboxes get acceptable performance. The indexes, once established, are updated by Exchange whenever the inbox changes (new message added, marked read, removed...). There can be a window of time from when a subscriber is added and their indexes are up to snuff, however.
So, assuming you're on 4.1 or later and using Exchange, I don't believe there is any specific mailbox limit where UM performance will start to break down.
