I just tested sending an email to my Exchange account at work and it showed up on my iPhone 4 running 4.0.1, so it can still work. We run Exchange 2007, do you know what version your Exchange server is?
If you want to go back to 4.0.0, did you back up your SHSH file using an application like Umbrella? If not, I don't think you can go back.