ｺﾒﾝﾄに書いたことと重なりますが､ここでは｢こういう時に自分がやること｣という観点で書きます｡

1. VLOOKUP関数の利用の見直し､その1｡VLOOKUPでやる処理をVBAで書き直す｡
特に検索するのが同じﾃｰﾌﾞﾙの中だったりすると､新しいﾃﾞｰﾀを追加する度に古いﾃﾞｰﾀも新しいﾃﾞｰﾀをふまえて再計算､ということになりかねません｡計算量が爆発してしまいます｡
ﾃﾞｰﾀの変更をﾘｱﾙﾀｲﾑで反映するのがLOOKUP系関数のｳﾘです｡ﾘｱﾙﾀｲﾑでなくて良い場所はLOOKUPを使わず､VBAで直接書き込んだり､一旦VLOOKUPで得た結果を値ｺﾋﾟﾍﾟして再計算させないようにしたり……といったことをします｡

2. VLOOKUP関数の利用の見直し､その2｡VLOOKUPで検索する場所を別の表に切り出す｡
容易に増えるﾃﾞｰﾀ(例：ｺﾞｷﾌﾞﾘ)と､あまり増えないﾃﾞｰﾀ(例：ｺﾞｷﾌﾞﾘが棲む都道府県)が別立てになれば､多少爆発の勢いを押さえられるかもしれません｡
これが出来るかどうかはﾃﾞｰﾀの内容によります｡

3. 処理の分割｡集計の場合､100万件を10万件に､10万件を1万件に集約してから他の加工を行うなど｡

4. Excel以外のｿﾌﾄに乗り換える｡
今でこそ仕様上可能ですが､100万件というのはExcelで扱うには大きすぎるﾃﾞｰﾀ量です｡他方､Accessやその他DB系のｿﾌﾄはこの手の大量ﾃﾞｰﾀを扱うのが得意だったりします｡
現実にはAccessでも対応しきれなくて､多数のｻｰﾊﾞに処理を分散して実行するHadoopなどの助けを借りるようなものもあり得ますが､そこはもう素人には……｡

1,2,3どれが効果あるか､楽か､実現可能かは扱うﾃﾞｰﾀと欲しい結果に寄ります｡自分はまず3から考慮します｡3の観点でなんとかできるものは将来的にも問題を起こしにくいので｡
ﾊﾟﾌｫｰﾏﾝｽの問題を起こすのは簡単ですが､解決はｿﾌﾄｳｪｱの技術を学ぶ学生､職業ﾌﾟﾛｸﾞﾗﾏでも考え込んでしまう問題で､職業ﾌﾟﾛｸﾞﾗﾏでも不得意な人が多いです｡なので､まずは量を押さえ込む工夫を｡他はそれからの問題としても良いと思います｡

こちらの書籍が参考になると思います｡入手がちょっと難しいかもしれませんが｡

Excel VBA ﾊﾟﾌｫｰﾏﾝｽﾚﾎﾟｰﾄ

http://www.amazon.co.jp/Excel-VBA-%E3%83%91%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%B3%E3%82%B9%E3%83%AC%E3%83%9D%E3%83%BC%E3%83%88-%EF%BC%B3%EF%BD%8F%EF%BD%8D%EF%BD%85%EF%BD%94%EF%BD%88%EF%BD%89%EF%BD%8E%EF%BD%87-%EF%BC%B5-%EF%BD%97%EF%BD%81%EF%BD%8E%EF%BD%94-%E5%9D%AA%E5%B4%8E/dp/4904412079/ref=pd_sim_b_4#_