Randomly losing CMD+V (paste) functionality
I had the same issue, what I found was that using a Software called ShareMouse, and when it crashed, I lost my Cmd+v functionality; I then forced ShareMouse to close, and cmd+v returned. 

You may be experiencing this issue with ShareMouse, or some other piece of software.