I'm surprised at these results - I would imagine that, as a user, I'd be confused when objects or functions disappeared from view. If the 'adaptation' isn't well signposted, I could confuse a 'rearrangement' for a change in state, user permissions or something else that 'locks me in' to a certain sort of behaviour. As a user, I would immediately assume I'd changed my app's "mode" in some way, and rather than seeking the hidden control, I'd look for the controls that effected this 'mode'.
As such, I would suggest that you only provide an adaptive UI with certain precautions, and with three specific caveats:
One: Ringfence the 'adaptive' part of your UI into its own widget or visually distinct control. Combine it with other 'context-sensitive' functions, so the user still trusts the rest of the application
As a user, I don't generally expect menus and the like to change. If things started moving around, I might stop trusting the rest of the application to remain static. If, however, the 'adaptation' was limited to its own visually distinct area (like a floating 'context' window), and its nature was well communicated (with a title like 'You might want to...', for example), I could reap the benefits of an adaptive UI without losing trust in the rest of the application.
Another advantage of this approach is that you can include other 'context-relevant' content beyond just controls and data. Imagine my 'You might want to...' window suggesting context-sensitive help articles, or articles on interesting effects and tips. Imagine it even crawling the web for relevant content! By distinguishing your 'experimental and amorphous' component from the 'rest' of the application, you can exploit 'context-sensitive' without losing your users trust, or creating an application that looks half-finished or unreliable.
Two: Make sure your 'relevance' algorithms are up to the job
If you're going to change a UI mid-use, you must make sure it actually does make the program more relevant and useful. If I repeatedly add headings then bullets, I don't want my bullet controls to disappear on the third heading, just because your app thinks "three headings = lots of document structuring = unlikely to add new bullet content". You should rely on empirical data and be able to spot quite complex patterns, else you risk letting your users down. Every time your adaptation frustrates your user, you lose far, far more goodwill than when it improves UI relevance.
Three: Let users turn it off!
Worst comes to the worst, at least let users switch adaptation off. Let them reset their usage history and go into 'non recorded' mode (so a friend taking over, or an unusual task don't 'mess up' the context-arranged controls). This way, even if your risky 'adaptive' UI doesn't pay off for certain groups, your risk is mitigated.