just had a play with this, and I think you have uncovered a bug (or at least an undocumented "feature"),
Could you try this? Open a new workspace (easiest is to quit and restart), then copy a word (using whatever process you like) and then click in the search all bar, and press CMD-V. I think you will find that will work.
However, if you go via the "Edit" menu, the "Paste" options are greyed out, and if you right click in the search all box, you just get the search all options dropping down.
Could you just confirm this is what you see as well?
Joel, this seems to be a bug to me.