I used a different unlock service but just to confirm:
The IMEI code that you sent them was 15 digits, and
The unlock code that you received back was 16 digits?
The unlock code is calculated based on your IMEI, so an incorrect IMEI will generate in incorrect unlock code. Just confirming, no insult intended.
Edit: the 'not found' error from the first guy might be an indication of an IMEI number problem, the second might attempt to calculate the code without verifying the number of digits (just guessing).