Hola, just registered to post this:
Started using this amazing tool (the Pokechecker, that is, though the legality checker is nice too) today and wanted to check the PID on a Garbodor I just caught on Route 9 to try and diagnose why my RNG abuse failed. When I did so, I also clicked on the legality checker for no apparent reason, but surprisingly it turned up a false positive -- the checker thought the Garbodor was hacked in because it was underleveled. They don't normally evolve til 36, but you can catch them as low as 33 in Route 9.
Link to the guy: http://pokecheck.kraftpaper.org/?p=detail&uid=102440 (don't know if this will work, I haven't messed with any public / private settings yet)
I know there are quite a lot of pokemon like this, where you can catch them slightly or significantly underleveled, sometimes massively so like the Electrode you can get at level 2 (IIRC), so if you intend to tackle them all... good luck.