[SalesForce] Approval process Final Rejection email alert not working

I'm building an approval process in which I need a record to be submited to approvers in a queue, and the record gets approved or not. It's a simple one-step approval.

I've set up an email alert for cases when the record is rejected, so its owner knows that it wasn't approved. But I want to use a organization-wide address (like logistics@company.com) for this.

The organization already has addresses available for use (for all profiles) (and in use in other processes using scheduled classes), and the address I want to use is registered in the organization-wide address setup page.

The problem is: the email alert seems to work only when the email alert uses the Current User's email address option. Any ideas why? Or how can I make the Final Rejection step work with an org-wide address?

Edit:

After @gorav's suggestion, I checkd the email logs on my organization, and some emails did bounce back because of the DMARC policy. The log entries have a message like this:

550-5.7.1 Unauthenticated email from thecompany.com is not accepted
due to\r\n550-5.7.1 domain's DMARC policy. Please contact the
administrator of\r\n550-5.7.1 thecompany.com domain if this was a
legitimate mail. Please visit\r\n550-5.7.1
https://support.google.com/mail/answer/2451690 to learn about
the\r\n550 5.7.1 DMARC initiative. – gsmtp

So now I want to know: being in a company that has its own domain already defined, and using Google Apps for business, how can I get Salesforce to deliver emails with the addresses I specify? Should I get the DKIM keys for the company's domain? Is it the only step required?

Edit (24/01/2017):

I've requested the keys from the company's domain admin and he provided me with both keys and I imported them to sandbox, but still the emails are bouncing due to DMARC's policy, with the message quoted above. What do I need to do to make Salesforce send emails on behalf of the company domain?