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.