Lower Bounds for Data Structures 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?
There is a really nice talk on the dynamic lower bounds on graphs by Mihai Pătraşcu. In summary (on p.20 of the slides), we have the lower bounds in terms of query time $t_q$ and update time $t_u$ (insert an edge):



See the paper for details. Some other papers by Mihai are relevant and nice, too.

UPDATE: I found that his PhD thesis "Lower Bound Techniques for Data Structures" providing lower bounds for many central data-structure problems using the techniques he developed. It certainly worths a read.