That's a very good match. The fact that he doesn't match any of your matches is not surprising. It's actually rather hard to find matches that line up that way. Your new cousin might want to recruit some known cousins from different sides of his family. That would serve to confirm his paper trail is correct (no unrecorded adoptions, etc) and give more data points to compare with your side.