Those are not REST because they are not resource-based.
Correct REST:
http://blah.com/widget/:id - GET, PUT, POST, DELETE
How does that fit with your /rdio/4E7?q=1 ? Where's the resource? What is the id? What is q anyway?
You can pass parameters with a ? in REST... for example, you might do
GET http://blah.com/resource/123?format=xml
But there's still a clearly identified resource which the GET is performed on.
Sure, technically, by stretching things a bit, you could claim that /rdio?q=1&s=63-8 is a REST GET request for resource id "63-8".
And, technically, you'd be right, much like technically, this is valid C: http://stackoverflow.com/questions/18642/what-is-the-most-un...
But just because it's valid doesn't mean it's in any way good. Those are horrible examples. So no, those URLs could not "just as well" be those nasty examples you give. They could, much more poorly, be those examples, and still be technically valid. By the same reasoning, "Buffalo buffalo Buffalo buffalo buffalo buffalo Buffalo buffalo" is just as good english as Shakespeare.
Your arguments about nice looking URLs in fact have absolutely nothing to do with REST, except that REST says you must use your transport protocol according to its standards, where appropriate. It says nothing about how URLs should look. I you're talking about the HTTP spec, call it by its proper name please. We don't gain much from conflating different terms like this, it's just a source of confusion.
There is absolutely no difference between path segments and query parameters from the perspective of resource identification.
Sorry sir, I'm not wrong, those would be perfectly valid as part of a REST service, including as alternatives to tptacek's description. Readability of the URLs has nothing at all to do with RESTfullness.
The only thing REST says about the data transmitted (the URL in this case) is that it's the container for the application's state, and most interpretations of this is that the URL is entirely opaque. And indeed, Fielding has suggested/explained this several times.