[Exim] Authentication/Relay problems

I'm having a pretty serious problem with making Authentication and Relaying
work the way I want. I am using Exim 3.12 on debian 2.2, and here is the
important stuff from exim.conf:

Main section:

host_auth_accept_relay =*
host_accept_relay = localhost:127.0.0.1

Very Last section:

login:
driver = plaintext
public_name = LOGIN
server_prompts = "Username:: : Password::"
server_condition = "${if
crypteq{$2}{${extract{1}{:}{${lookup{$1}lsearch{/var/mail/config/auth.users}{$value}{*:*}}}}}{1}{0}}"
server_set_id = $1

I am mainly using Windows Eudora as the mail client, and have been testing
it extensively on 3 remote machines. Two machines are completely remote and
cannot relay at all, and receive the standard 550 error, even though they
are set to use Authentication. The third machine is behind the same
firewall as the server, and seems to authenticate and relay perfectly. The
ONLY way I can get the other two clients to properly relay messages is to
add their hostname to the host_accept_relay section. This works, but this
list will grow quite quickly as my userbase qrows as well. It also does not
help if I have a few mobile users that dial up from different locations.
I'm REALLY stumped. Any ideas?