Update: The change described below does not seem to have reliably stopped Google from bouncing my e-mails. Time to ask them what they're doing...

I obviously spoke too soon. Having complimented Google for finally enabling IPv6 on Google Apps, I was lying in bed this morning firing off a few e-mails from my phone when this bounce came back:

This message was created automatically by mail delivery software. A message that you sent could not be delivered to one or more of its recipients. This is a permanent error. The following address(es) failed:

[email protected]

SMTP error from remote mail server after end of data:
host ASPMX.L.GOOGLE.COM [2a00:1450:400c:c05::1a]:
550-5.7.1 [2001:41c8:10a:400::1 16] Our system has detected that this 550-5.7.1 message does not meet IPv6 sending guidelines regarding PTR records 
550-5.7.1 and authentication. Please review 550-5.7.1 https://support.google.com/mail/?p=ipv6_authentication_error for more 550 5.7.1 information. ek7si798308wic.60 - gsmtp

Hmm. The recipient address has been changed, but the rest of the above is verbatim. The page Google link to says:

"The sending IP must have a PTR record (i.e., a reverse DNS of the sending IP) and it should match the IP obtained via the forward DNS resolution of the hostname specified in the PTR record. Otherwise, mail will be marked as spam or possibly rejected."

All of which is reasonable-ish, but the sending IP does have a PTR record which matches the IP obtained by forward resolution:

david@jade:~$ host 2001:41c8:10a:400::1
1.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.0.4.0.a.0.1.0.8.c.1.4.1.0.0.2.ip6.arpa domain name pointer diamond.dnorth.net.

david@jade:~$ host diamond.dnorth.net.
diamond.dnorth.net has address 212.110.165.240
diamond.dnorth.net has IPv6 address 2001:41c8:10a:400::1

So what are they objecting to? Some Googling and some speculation suggests that they might be looking at all hosts in the chain handling the message (!). Further down the bounce in the original message text we find:

Received: from [2a01:348:1af:0:1571:f2fc:1a42:9b38]
	by diamond.dnorth.net with esmtpsa (TLS1.0:RSA_ARCFOUR_MD5:128)
	(Exim 4.80)
	(envelope-from [email protected])
	id 1Vrm3Q-0002Ay-NH; Sat, 14 Dec 2013 10:02:36 +0000

Now, the IPv6 address given there is the one my phone had at the time. It doesn't have reverse DNS because you can't disable IPv6 privacy extensions in Android (also Google's fault!), and assigning reverse DNS to my entire /64 would require a zone file many gigabytes big.

At this point, it's probably best to stop speculating on Google's opaque system and start working around it from my end. Others have resorted to disabling IPv6 for their e-mail server altogether - no thanks - or just for sending to gmail.com. This latter approach doesn't work for me as the example above involves my-friend-with-google-apps.example.com - and potentially lots of different domains will be using Google Apps for mail, so a simple domain-based white/blacklist isn't going to cut it.

After spending some time with the excellent Exim manual, I've come up with a solution. It involves replacing the dnslookup router with two routers, one for mail to GMail/Google Apps hosted domains, and one for other traffic. Other settings on the routers are omitted for brevity, but you should probably keep the settings you found originally.

dnslookup_non_google:
  debug_print = "R: dnslookup (non-google) for $local_part@$domain"
  # note this matches the host name of the target MX
  ignore_target_hosts = *.google.com : *.googlemail.com
  # not no_more, because the google one might take it

dnslookup_google:
  debug_print = "R: dnslookup (google) for $local_part@$domain"
  # strip received headers to avoid Google's silly IPv6 rules
  headers_remove = Received
  headers_add = X-Received: Authenticated device belonging to me or one of my users
  no_more