OK, I also noticed sometime during the summer that my calendar was no longer updating. Then I had all my Outlook contacts disappear from my phone in August only to return hours later. This week I received a replacement for my failed SGSII. I came back to this thread and redid my setup from the first post, but days later I have yet to see anything from Outlook sync with the phone. When I try to force sync on the phone the icon spins for less than a second and disappears. Reading about the server issues above it appears they have been corrected and this should still be working. This had been working flawlessly for me for over a year. Any ideas?
UPDATE: I finally got sync working again. After following the instructions on page 1 about half a dozen times with no success I decided that instead of creating the Exchange account from within the e-mail app on the phone I would do it through the Settings>Accounts and Sync area. This was the charm and my Outlook contacts and calendar are now syncing as before.