What about user groups? Can you follow that group pattern?
3000 machines in one group is still OK, 5000 being barely acceptable. But it depends a lot on our server storage performance and database tuning (index/cache is a must).
As Peter says, there is no hard limit - well, 2^32 I guess it you want me to quote the design spec, but as the size of a group gets bigger, you run a higher and higher risk of hitting a transaction timeout, just because things take longer. The default transaction timeout is 30 seconds, after which it gets aborted, so as long as any group operation takes less time than that (or you increase the limit), nothing much will go wrong.
When a group operation times out though, normally it either gets zeroed, or significantly truncated, that's where orphans come from - they are the result of a succesful remove from one group, and a failed add on another.
So, get a chunky server and 3-5K is no problem, slow server, 500 may be an issue with the default timeouts. You can always change them though.