550 5.7.1 unable to relay in application

Hello all!
I have been trying to deal with a very strange problem for days now, and would appreciate any help you could give me!

As of last Thursday, our sales team is no longer able to send e-mails through an application we use to mail invoices. It worked fine for six months before that...

Here are the facts:
•We have a sales group using Microsoft Dynamics Great Plains 2010 and a 3rd party add on known as Salespad.
No configuration changes have been made.
•We have a server running Windows Server 2008, Exchange 2007.
No configruation changes have been made.
•It worked up until last Thursday.
•People can send e-mails just fine using outlook or OWA, just not through this third-party add-on to Great Plains.
•The error message presented is: 5.7.1 Unable to Relay.

Thanks again for any help!

EDIT: 12:26 pm
After enabling some more diagnostics, I found this in the event viewer:

Warning 3/22/2012 12:17:24 PM MSExchangeTransport 1035 SmtpReceive
Log Name: Application
Source: MSExchangeTransport
Date: 3/22/2012 12:17:24 PM
Event ID: 1035
Task Category: SmtpReceive
Level: Warning
Keywords: Classic
User: N/A
Computer: <<OUR MAIL SERVER>>
Description:
Inbound authentication failed with error LogonDenied for Receive connector “Internal server relay”. The authentication mechanism is Ntlm. The source IP address of the client who tried to authenticate to Microsoft Exchange is <<IP ADDRESS OF COMPUTER>>.

The error you are getting is caused because the application is trying to use your SMTP server to send mail. The server is rejecting that mail because the application is failing to authenticate with the server.

How does the application send mail to people? For example, does it authenticate to your Exchange server using a user account; is that account still active, has the password been changed? You can try enabling the local IP of whatever computer hosts the application for relaying.