私はかつて同様の問題を抱えていましたが、正確なアプローチはデータの内容によって異なります。たとえば、私はあなたに、1日あたりのリクエストの上限が非常に高い米国の郵便番号をジオコードできるサービスをいくつか見てきました。
私のケースでは、データはヨーロッパの国の住所だったので、Microsoft、Google、Yahooなどの大企業の公開APIが残っていました。
申し訳ありませんが、要求の日時と使用条件を読んだあと、すべてのアドレスをジオコードするには時間がかかりすぎることに気付きました。私はオープンストリートマップを見つけました。必要な地域のデータを自由にダウンロードし、解析し(XMLで)、データベースにロードして(私の場合はPostgreSQLを無料で)、独自のジオコーダを書くことができます。
確かに、すべてのアドレスを見つけることはできませんが、問題のあるアドレスを保存してGoogleなどのAPIを使用して問題を解決することができます。私の場合、それは私が始めていたすべてのデータのほんの一部であったので、それは価値がありました。
また、入力データに上限があると思われるMicrosoft API(これはよく慣れていない)についても同様の質問があるので、this answerをチェックしてください。