First, I think Excel has (or had) a limit. Do you really have a list of a half million records in Excel?
MapPoint slow for bulk geocoding and not that graceful with handling non-matches, but I'd imagine it can be done. Search this site for geocoding, also there are a couple articles here:
http://www.mp2kmag.com/a95--Geocodin....mappoint.html http://www.mp2kmag.com/a98--Geocodin....mappoint.html
best,
Eric