This isn't happening to every FRG22D / Exchange user. I'm running FRG22D and I've been getting Exchange mail from my work since I loaded it, and have had no functional change related to security on my Droid, nor have I had any stability issues related to accessing EMail. I suspect my Exchange server at work simply is not using whatever feature causes these issues.
Because this doesn't happen to everyone using FRG22D and Exchange, VZW is going to have trouble really finding out what is going on. They may forward the issue on to Moto and/or Google. But in the mean time they did the right thing in sending another phone out to you, their charter is to get you running again ASAP.