To fix the issue where android does this:

IPv6 address/MAC address sanitized

 31.855405 2607:f4b8:2600:1::1 -> 2607:f4b8:2600:5:b607:f9ff:xxxxxx:xxxxx SMTP Response: 220 ignignokt.timminstechnologies.com ESMTP Exim 4.69 Mon, 08 Aug 2011 00:28:43 -0400
.....
 31.857239 2607:f4b8:2600:5:b607:f9ff:xxxxx:xxxx -> 2607:f4b8:2600:1::1 SMTP Command: EHLO 2607:f4b8:2600:5:b607:f9ff:xxxx:xxxx
....
 31.862978 2607:f4b8:2600:1::1 -> 2607:f4b8:2600:5:b607:f9ff:xxxxxx:xxxxxx SMTP Response: 501 Syntactically invalid EHLO argument(s)
....

Do this in your exim4 config, and restart exim:

helo_allow_chars = _:

Technically, only the colon is necessary, but the underscore fixes some other handsets that use the android_aklsjdfljasdf style names in ehlo instead, also a bug.

More details:
http://code.google.com/p/android/issues/detail?id=13681