I'd say go for the police. Most ppl are scared shitless of them, and they might turn over their phone-stealing friend when getting pumped by the cops. What better revenge than if the cops get the guy? And you might even get ur phone back if ur lucky.
And, whatever happens, you still have those #'s to mess with. Even if you can't find any info on them, you could harass the hell out of them.
Were they cell #'s the guy called? I dunno how many cell carriers this works with, but I know it works with mine (Veroooozen)...lookup which carrier theyre with and get a friend with the same carrier to log in to their vm and use the option to send a message. After punching in the destination #, VZW will play that person saying their own name, which almost everyone does when they initally set up their vmail. Then just cancel the message send. It's a fun way to take a random # and get a name from it. And then zabasearch usually does the rest.
Let us know how the situation develops