Another solution which works in Debian is to modify /etc/hostname so it has a qualified name. For example, you could change this:
My prefered solution, though, is to not install exim4 in the first place. I like to start with a minimal install (not even the so-called "base" suite selected), and only install what I want. I don't know what depends on exim4, but so far I haven't ever installed anything that requires it.