After testing much and retracing my steps, I still cannot get google mail to validate.

My mail server is Debian 5.0 with exim

Exim version 4.72 #1 built 31-Jul-2010 08:12:17
Copyright (c) University of Cambridge, 1995 - 2007
Berkeley DB: Berkeley DB 4.8.24: (August 14, 2009)
Support for: crypteq iconv() IPv6 PAM Perl Expand_dlfunc GnuTLS move_frozen_messages Content_Scanning DKIM Old_Demime
Lookups: lsearch wildlsearch nwildlsearch iplsearch cdb dbm dbmnz dnsdb dsearch ldap ldapdn ldapm mysql nis nis0 passwd pgsql sqlite
Authenticators: cram_md5 cyrus_sasl dovecot plaintext spa
Routers: accept dnslookup ipliteral iplookup manualroute queryprogram redirect
Transports: appendfile/maildir/mailstore/mbx autoreply lmtp pipe smtp
Fixed never_users: 0
Size of off_t: 8
GnuTLS compile-time version: 2.4.2
GnuTLS runtime version: 2.4.2
Configuration file is /var/lib/exim4/config.autogenerated

My remote smtp transport configuration:

remote_smtp:
  debug_print = "T: remote_smtp for $local_part@$domain"
  driver = smtp
  helo_data = mailer.mydomain.com
  dkim_domain = mydomain.com
  dkim_selector = mailer
  dkim_private_key = /etc/exim4/dkim/mailer.mydomain.com.key
  dkim_canon = relaxed

.ifdef REMOTE_SMTP_HOSTS_AVOID_TLS
  hosts_avoid_tls = REMOTE_SMTP_HOSTS_AVOID_TLS
.endif
.ifdef REMOTE_SMTP_HEADERS_REWRITE
  headers_rewrite = REMOTE_SMTP_HEADERS_REWRITE
.endif
.ifdef REMOTE_SMTP_RETURN_PATH
  return_path = REMOTE_SMTP_RETURN_PATH
.endif
.ifdef REMOTE_SMTP_HELO_FROM_DNS
  helo_data=REMOTE_SMTP_HELO_DATA
.endif

The path to my private key is correct.

I see a DKIM header in my messages as they end up in my gmail account:

DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=mydomain.com; s=mailer;
    h=Content-Type:MIME-Version:Message-ID:Date:Subject:Reply-To:To:From; bh=nKgQAFyGv<snip>tg=;
    b=m84lyYvX6<snip>RBBqmW52m1ce2g=;

However, gmail headers always report dkim=neutral (no signature):

dkim=neutral (no signature) [email protected]

My DNS results:

dig +short txt mailer._domainkey.mydomain.com
mailer._domainkey. mydomain.com descriptive text "v=DKIM1\; k=rsa\; t=y\; p=LS0tLS1CRUdJ<snip>M0RRRUJBUVV" "BQTRHTkFEQ0J<snip>GdLamdaaG" "JwaFZkai93b3<snip>laSCtCYmdsYlBrWkdqeVExN3gxN" "mpQTzF6OWJDN3hoY21LNFhaR0NjeENMR0FmOWI4Z<snip>tLQo="

Note that the base64 public key is 364 chars long so I had to break up the key using bind9.

$ORIGIN _domainkey. mydomain.com.
mailer                  TXT     ("v=DKIM1; k=rsa; t=y; p=LS0tLS1CRUdJTiBQVUJM<snip>U0liM0RRRUJBUVV"
                                "BQTRHTkFEQ0JpUUtCZ1<snip>15MGdLamdaaG"
                                "JwaFZkai93b3lDK21MR<snip>YlBrWkdqeVExN3gxN"
                                "mpQTzF6OWJDN3hoY21L<snip>Ci0tLS0tRU5E"
                                "IFBVQkxJQyBLRVktLS0tLQo=")

Can anyone point me in the right direction? I would really appreciate it.