Web Services, Queues, polling them... best practices?

[eluser]andjules[/eluser]
Hi, looking for the opinion of more experienced developers (than me)...

I'm building an app that uses web services (for uploading, transcoding, image manipulation, etc.)... Most of the critical calls to the web services either i) are processed immediately, or ii) file a callback to me when they're done processing.

HOWEVER, there are a few instances where processing might take a while, and the service API doesn't fire a callback on completion, so:

It seems if something isn't ready when I first request it, I need to set up a queue, then poll the queue and re-check, until the service is done processing the original request, at which point I delete from the queue.

a) I'm aware of Amazon SQS, I'm aware of Apache MQ (which I keep hearing is a pain), are there any other local PHP practices for creating a queue (memcached?)?
b) what's the best practice for polling the queue? Cron? (that doesn't seem very elegant...)

Thanks in advance