I actually placed that line of code into the Default.aspx page: ((MasterPage)Master).myAjaxManager.AjaxSettings.AddAjaxSetting(((MasterPage)Master)myTree, myGrid) ). This is done in the PreRender method (actually, if I place it in the Load method, it doesn't work either).
However, I actually solved the problem, but I'm not sure what exactly caused it to work. I now use a RadAjaxManagerProxy directly on the page (instead of casting the Master property) and everything works fine. It's somehow random, I can't reproduce the error at the moment (Heisenbug?). I think I just handled the usage of the Cache in a wrong way. I accessed the Cache from the wrong places. Now I placed the Cache operations into event handlers and methods that return the actual data (yes, I was doing it wrong, somehow).
Thanks for that link. I had a look at it when the problem arised, but it didn't help.
I think the problem is solved now. If the problem should appear again, I'll have a deeper look at it. For now everything just works, and that's fine for me :)
Thanks for your time and help.