Hmmm, I thought I had already posted a reply to this... it must not have gone through, sorry.
Unfortunately I think you're right; there's no way to make the instanced geometry aware of per-particle attributes.
What you'd have to do, if you really can't get away with sprites, is create as many separate pieces of geo as you have images, which of course is a bit of a problem if you have thousands of them.
Maybe a workaround is possible if you can have the shader rely on some attribute like rotation or scale that is being set by the instancer... but I don't know if those values from the instancer replace the original object's values at render time or if they are just added to them the way a parent's are.
I think Houdini can do this, but Maya seems to be limited. :(
Sorry I couldn't be of more help. Maybe someone else can suggest something...