BlackBerry and Exchange 2007 daily password reset

We have a few BlackBerry devices on the Verizon network, using the Verizon BIS to contact our Exchange 2007 server to sync e-mail via ActiveSync.  It works fine, except every day, our three users that have these same devices are asked to update their password on a daily basis.  If they don't do this, e-mail will not get synced.  After they do this, the e-mail starts flowing.

We've tried a multitude of things to fix this issue.  I've contacted Verizon and had them make sure everything is correct in the account, and it is.  The set up has been done multiple times on the BB to make sure everything is fine.  I've read various suggestions that I've tried, but they have not worked.  The last thing I tried was to change the server to connect to https: as part of the URL to the OWA server.  I should note that we have a self-signed SSL cert.

Anyone have any ideas?

E-mail:
From: donotreply@blackberry.com
To: x@y.com
Subject: Action required: update password!
Sent: Jan 22, 2009 2:53 AM
 
Update the password for x@y.com in the BlackBerry Internet Service! Email messages from x@y.com are not being delivered to your BlackBerry device. To resume receiving email messages from this email address, update the password for x@y.com in the BlackBerry Internet Service:
 
 1. Open your BlackBerry Internet Service account by completing one of the following actions:
 
 * Click the email setup application on your device.
 * Using a browser on your computer, visit the BlackBerry Internet Service web site.
 
 2. Go to the Email Accounts page.
 3. Edit x@y.com.
 4. Update the Password field.
 5. Click Save.
 
Email Account Information:
Email Address: x@y.com Email Account Name: x@y.com
 
-- Automatically generated email: Do Not Reply to this email --

Select allOpen in new window