I like to start with REST, I feel it's a great canvas, and a great way to think about what I am delivering. And if I can get the design to work within it's confines, then that's what I'll go with. It almost never ends up fully RESTful, and that's usually because the complexity required in the code would impact the maintainability. And to me maintainability is usually more important.