Are results known which rule out the existence of "too-good-to-be-true" data structures?
For example: can one add $Split$ and $Join$ functionality to an order maintenance data structure (see Dietz and Sleator STOC '87) and still obtain $\mathcal{O}(1)$ time operations?
Or: can one implement an ordered set with integer keys and $\mathcal{O}(1)$ time operations? Of course this is at least as hard as discovering a linear time algorithm for sorting integers.
Has the answer been proven to be no for either of these questions? Are lower bound results known for any natural data structure?