Ask HN: Designing a REST API

I am in the middle of building a REST api using Rails. Basically a client app can post to the api with a message and an author. The service then figures out what to reply and who to reply to in a background process.

My question should I design it so that the api posts back to the client's callback url when the reply message has been calculated (similar to Paypal IPN) or should the I design it so that the client must poll the server to see when the reply has been generated?

e.g.

Polling solution Client app: POST myapi.com/messages

then poll GET myapi.com/messages/2324

Callback URL solution

Client app: POST myapi.com/messages

server: POST clientapp/messages

My initial thoughts are that a callback url is better because less requests have to be made from the client to the server. And the client app will also be simpler and more responsive since there is no polling required. But this doesn't seem very RESTful? Should I care? Are there any advantages of having polling solution that I'm overlooking?