I use YankRing (http://www.vim.org/scripts/script.php?script_id=1234) which takes care of the problem of remembering yank history. Just map :YRShow to a key and you are good to go.
So by repeatedly hitting ^p after a paste you can cycle back quite a ways. Way easier than ":reg, now where did that go?"