"Last Come => More Relevant" data structures
I think of three possible options:


As mentioned before in the comments, one of my all-time favorite data structure, splay-trees. They are easy to implement and probably (assuming the Dynamic Optimality conjecture is true) roughly as good as any other dynamic search tree data structure. We already know that splay trees are as good as any static search tree. Note that there are other types of dynamic binary search trees (tango trees, zipper trees, ...), which will also perform well compared to the best dynamic search tree.
Use one or more optimal binary search tree (via dynamic programming). Since you insert/delete elements you need to rebuild the search tree form time to time. Say after a threshold value of elements that change you build the new optimal tree from scratch. This might be applicable, if you have time between the request. The rebuilding can be also be done in the background. Since building a optimal search tree is $O(n^2)$, this is not a good idea for large data sets. 
Use Hashing. It might not treat the later inserted elements different, but in practice it might be as good as the other ideas.


You might think of keeping the last inserted elements in a separate data-structure (like a hash-map ) which you query first. Of course, from time to time you need to rebuilt.