I do think there should be passport stamps (my passport has them), but if not, there should be airline tickets (which if discarded I am sure the airline could corroborate were purchased, etc.). That is why it is clear he is lying.