[exim] rejected RCPT, relay not permitted

I'm setting up exim on a new server, "newserver.test.com". Whenever I send
test messages from Alpine / PINE from either the localhost (same as
newserver.test.com) or a different host that's configured to look at the new
server, I get the following messages in my mainlog:

To a gmail account:
2009-04-23 15:49:33 H=newserver.test.com [xxx.xxx.xxx.xxx] F=<
testuser1@???> rejected RCPT <testuser2@???>: relay not
permitted
2009-04-23 15:49:35 1Lx6nX-0001JT-Nf <= testuser1@??? H=
newserver.test.com [xxx.xxx.xxx.xxx] P=esmtpsa X=TLSv1:AES256-SHA:256
A=dovecot_plain:testuser1 S=574 id=
alpine.GSO.2.00.0904231549210.5048@???
2009-04-23 15:49:36 1Lx6nX-0001JT-Nf => testuser2@??? R=dnslookup
T=remote_smtp H=gmail-smtp-in.l.google.com [209.85.147.27]
2009-04-23 15:49:36 1Lx6nX-0001JT-Nf Completed

To user on another server in same subnet/domain:
2009-04-23 15:49:48 H=newserver.test.com [xxx.xxx.xxx.xxx] F=<
testuser1@???> rejected RCPT <testuser3@???>:
relay not permitted
2009-04-23 15:49:48 1Lx6nk-0001JY-ST <= testuser1@??? H=
newserver.test.com [xxx.xxx.xxx.xxx] P=esmtpsa X=TLSv1:AES256-SHA:256
A=dovecot_plain:testuser1 S=589 id=
alpine.GSO.2.00.0904231549360.5048@???
2009-04-23 15:49:49 1Lx6nk-0001JY-ST =>
testuser3@???=dnslookup T=remote_smtp H=
oldserver.test.com [xxx.xxx.xxx.xxx]
2009-04-23 15:49:49 1Lx6nk-0001JY-ST Completed

Rejectlog shows:

2009-04-23 15:49:33 H=newserver.test.com [xxx.xxx.xxx.xxx] F=<
testuser1@???> rejected RCPT <testuser2@???>: relay not
permitted
2009-04-23 15:49:48 H=newserver.test.com [xxx.xxx.xxx.xxx] F=<
testuser1@???> rejected RCPT <testuser3@???>:
relay not permitted

However, the mails are delivered fine, as expected. What is strange are
these 'relay not permitted' messages. I have tested with other clients,
including Mac Mail and Thunderbird, and do not see these messages in the
logs. It seems specific to al/pine only.

I do not have this issue on oldserver.test.com. Granted, it's a slightly
different setup- most notably not using dovecot and no encryption or
security.

Any ideas about what might be going on here? It's not a big deal seeing
that the messages are getting delivered, but I'd prefer not to see my logs
cluttered up with these seemingly bogus messages once I put
newserver.test.com into production.

Thanks, Renee