This problem persists. I'm not sure what other programs might interfere. I don't have any window managers installed that I know of, just OS X.
I notice it most in Chrome. Here is my exact display setup:
15" Macbook Pro internal display, 24" external display connected via displayport-to-dvi cable. My external monitor is set as the primary display, and I can only remember it happening when trying to paste into Chrome on the external monitor, while another Chrome window is also open on the internal display. In this case, Alfred always tries to paste into the Chrome window on the internal display.