As reported by this article http://www.tuaw.com/2009/09/10/iphone-os-3-1-now-enforces-exchange-encryption-policy-may-block/ you can get yourselves locked out from Exchange if the following conditions are true:

• You have an iPhone 3G device
• You upgrade to the OS 3.1 release
• and your Exchange Admin has enable the "Require Device Encryption" policy for Activesync.

Because the 3G model doesn't support device encryption it will now prevent you from accessing your exchange account and you will receive the message.

There are 2 supported options to fix this problem:

• Disable the requirement of Device Encryption in the Activesync Policy (but you enabled it for a reason the first time so that's not going to be a real option I'd say)
• Upgrade the device to a 3GS which has the built-in hardware to support device encryption.

Although inconvenient from an end-user perspective I still applaud the choice they made to fix that security hole. If the iPhone ever wants to become an enterprise ready device then this is what they need to do. In addition I hope to see that the iPhone will support more of the Activesync policies and perhaps even include an OMA-DM client so that we can manage it through Mobile Device Management solutions such as System Center Mobile Device Manager.

Sincerely,
Tonino Bruno | ICT Consultant | Pro-Exchange User Community