If the recipient claims to not yet have received their gift certificate, then you should advise them to check their spam folder, as some email hosting clients may automatically file the gift email into such a folder.