I have the same problem.
I have tried all the things listed above to no avail. My Lion installation is connected to an Exchange server and the only wierd thing about it is there are two accounts connected to the same server. When I go to the delegates section I get nothing - no names, no spinning wheels, nothing...
I have the accounts set up with all the synching options ticked as described above. Like the others in this forum, it works fine from an Outlook environment on Windows.
As a meta point why are there all these similar comments from users and nothing from Apple - even saying yeah we know about this problem would be good.
Making sure contacts syncing was enabled fixed it for me. Once it is enabled, I can see other users on the server and add delegates and grant access to my calendar. Then I cam turn off Contacts syncing and it still works.
Maybe that second account is the issue. You might try deleting both accounts and starting over, assuming the data will be preserved on the server.