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