Last fall Microsoft removed the Live Search Maps Add-in from availability due to a number of issues with it. A few weeks ago, the add-in stopped mapping addresses. Unless you need to it create travel time appointments, you should uninstall it.
How to remove the Live Search Maps Add-in for Outlook http://support2.microsoft.com/kb/961081
Published May 5, 2009. Last reviewed on June 17, 2011.