I already have almost 3 500 categories and need more and more at
http://zeno.ru. It is not dedicated server but one of thousands hosted by my ISP. I believe that PP can serve much more categories - at least, I can migrate to the dedicated server if I'll see problems with usability of the database.
But there is one problem that is really headach. If you are usual user, there are no problems. But if you have rights to move pages between categories, you are getting quite big file of the page because the whole list of categories should be inside the page for this moving option. And it will grow further and further while you are developing the categories tree.
Do you have any ideas how to resolve that problem? (Please do not offer 1 Gb connection for such user

)