"To look for evidence". This is frightening. Searching through something to look for incriminating evidence. It's the reverse of how the system is supposed to work.
I'd say they have reasonable cause to believe that they will find evidence in the messages.
(and I think I'm right in saying that the courts were't even involved, so the warrant part doesn't work either)
My thought process went a little like this...
Presumably the police could apply for a warrant to search RIM's premises for something along the lines of "records of messages used to organise a riot"? If they got that warrant, then they could go to the physical servers and search for the relevant data on site? AFAIK that's a perfectly feasible scenario and completely within the law - even though RIM haven't committed any crimes, I think they can still be the subject of a warrant. I'd guess something similar would happen in cases of fraud.
And if they can do that, then they could also ask RIM for permission to do it without a warrant. Which RIM might agree to if they believe that the police would get the warrant anyway.
And if they can do that, then it doesn't sound much worse to give the records to the police for them to search through using their own computer systems instead of going and searching directly on RIM's servers.