He probably had more information than your IP address.
I've tracked down two people on the 'net, but it was incredibly easy. Both of them gave out full names and the cities they lived in. It wasn't hard to look in the phonebook for those areas and find that they were listed.
In my defenne, though, both were harassing me. The latter one got my phone number from the whois information from the domain I own and was harassing me directly for banning him. Google XGMX and you'll find that he's a stupid little fucking troll everywhere he goes on the internet.