It's a good sign that REST is not perfect for everything. Trying to be everything to everyone is a trap that framework and API designers fall into. You should actually aim for making most people mostly happy, but leave some people rather bummed out.
(Google tech Talk on Designing an API.) http://video.google.com/videoplay?docid=-3733345136856180693
If your plans make everyone happy, you're probably trying to do too much.