I just noticed that when I receive a message from someone then their availability icon is shown correctly next to the last message from them. So the places it is missing from are address book, desktop shortcuts and conversations main window. MSN contacts still work fine.