The following is a description of the types of BES keys:
NAME Format (T=Temporary, S=Permanent)
SRP Identifier TXXXXXXXX or SXXXXXXXX
SRP Authentication Key xxxx-xxxx-xxxx-xxxx-xxxx-xxxx-xxxx-xxxx-xxxx-xxxx
CAL authentication key besx35-xxxxxx-xxxxxx-xxxxxx-xxxxxx
CAL ID Cxxxxxxxxxx
The x's represent alphanumeric characters. The important keys for maintaining connectivity to the BlackBerry Infrastructure (RIM's NOC) are a valid SRP ID & SRP Authen Key. The CALs (or new CALs) will not prevent expiration....they only allow you to add more accounts to the BES service.
Chances are you received a different SRP Authen Key to use with the same SRP ID. Only RIM can provide a "different" SRP Authen Key that will work with the same SRP ID. I had that done for a previous project awhile back. It's not a common occurence.
You could also go to the following site: http://www.blackberry.com/select/server/v41_trial.shtml
and download the latest version for trial testing. You'll be provided with a 60-day eval with temp keys. You may be able to use those keys in your current environment instead of waiting on the vendor.