Looks like the SMTP email header that your plugin is generating is not 100% correct.
The WP system email address (General > Settings) is still being included in the SMTP email header.
This is resulting in some email systems marking it as SPAM.
Can you please resolve this.
I added a comment about this on the support forum at http://wordpress.org/support/topic/plugin-wordpress-printable-gift-certificate-plugin-wp-gift-cert-certificate-email-not-being-sent?replies=10