I upgraded to Emacs 24.2.1, and things changed.
The attempted-paste now turns into an Emacs scroll-down-command. That makes sense if you know that scroll-down-command is invoked with Command-v. (Yes, Emacs is weird.)
So, I guess Alfred simply sends Command-v.
If I customise Emacs to bind Command-v to Emacs' version of paste (called yank), everything works nicely.
I'm pretty happy with this as a solution. Old-time Emacs hackers would probably find it annoying to have to rebind Command-v. It would be fantastic to be able to customise Alfred to send a user-specified character to Emacs (or more generally to specific applications). But if no-one is asking for it I wouldn't bother implementing it.
Thanks for listening.
-Simon