Dmitry, that's right, I don't have websites with so many categories.
The main website I'm working on, as webmaster, have 390 categories, and 10 languages. Let me tell you that at this point, it's even impossible to edit 5 categories at the same time, otherwise everything explode when I try to save changes! Not to say that Debug mode need to eat more than 50mb (!) to finish its output, giving the need to change mysql config, just to be able to work correctly... If you are interested by categories bug, I can provide you some recipes, even with my small websites :)
And categories "not appearing after creating" is a frequent bug, even on standard install with 10 new categories added. And until pressing "Refresh", no chance to view them (nor recipe here sadly).
That's why I propose to do it silently. Every time. For every sizes.