I have use GoogleRefine to query both nominatim and googlemaps api for this. I must say, I have never come remotely close to doing that many addresses. I know both sites have a limit on the number of queries a day (something like 2500 maybe?), and it may take a long time as there are some throttling blocks. I believe at least for the googlemaps stuff they have a pay service that removes those limitations.
I know that isn't a great answer, but maybe it will point you in a direction.