There are tons of reports on regenerating the offline address book and forcing outlook to download a new version once a change has been made, but that doesn’t really apply when outlook is not being used in cached mode.
I had renamed a couple of distribution lists but they were showing up as the old name in outlook for all my users. Turns out that I had renamed them on a server without the exchange add-ins which made it harder to troubleshoot as it all looked good on there! However, because of this I had not changed the Exchange General tab which includes the Display Name – sure enough this was showing the old name. I changed this and the users address book came up properly. Next time I’ll do ALL renames on my exchange server 😉