すいません、２行目のをはミスです。

また、縮小した後に連結～としていますが、
連結した後に縮小したほうがいいのかも？

StretchDIBitsとかでなんとかなりそうかも
しれません。

他には、色深度が全て共通であれば、それぞれのビットマップから1ピクセル置きにデー
タをコピーすることで、できそうな気がしますね。
そのとき、スレッド化すれば効率よく出来そう。

黒を連結先の左上にコピーする
順次右上、左下、右下も同様の処理を行う。
■□■□
□□□□
■□■□
□□□□
(X1Y1)

■■□□
■■□□
□□□□
□□□□
(連結先)

とりあえずメモリデバイスコンテキストを１つ用意しておく。
そこへ StretchDIBits 等を使って縮小した画像を転送(描画)。
※転送するときに縮小画像のサイズから描画位置を計算。

あとはメモリデバイスコンテキストに描画された内容を
そのまま１つのBMP画像として保存すりゃえぇよ。

> また、縮小した後に連結～としていますが、
> 連結した後に縮小したほうがいいのかも？
これってメモリが無駄になるから縮小画像を連結した方がいいと思う。
綺麗に縮小したいなら StretchDIBits を使わずに同等処理を実装。

StretchDIBitsを使うよりもDIBSectionとして読み込んで
StretchBltで転送した方が高速に動作します。
GDI+を使う場合は高品質な縮小描画も可能です。

ちょっと混乱しそうなので簡単に説明しておきます。

まず、 Windowsでビットマップを扱うためには、大きく２つの形式があるという
ことを覚えてください。
1) 通常の GDI ビットマップ(DDB形式)
2) DIB形式のビットマップ

形式を指定せずにビットマップを読み込んだ場合はDDB形式で読み込まれます。
その場合、StretchBlt()でビットマップを拡大縮小できます。
ただし、StretchBlt()を呼ぶ前に、SetStretchBltMode(HALFTONE)を忘れずに指
定してください。そうしないと縮小後のビットマップは汚くなります。
そこまでできたら、BitBlt()で目標の位置にビットマップを転送するだけです。

次にDIB形式ですが、ビットマップを読み込む際にDIB形式であることを指定しま
す。LoadImage()で読み込むなら LR_CREATEDIBSECTION を指定します。
この形式で読み込むメリットは、ビットマップをビット配列として扱えることで
す。ビット配列として扱うと、ビットマップのミラー反転，背景透過表示，...
などが簡単に行えます。
逆に言うと、ビット配列として扱う必要がない場合は DIB形式を使うのは、手間
が増える分損な感じです。
詳しくは以下のＨＰの[DIB]を参照してください。
http://eternalwindows.jp/graphics/bitmap/bitmap00.html

DIBとして読み込んだら、皆さんのおっしゃっているStretchDIBits()が使えます
し、DIBもビットマップに変わりないので、DDBのときと同じようにStretchBlt()
で縮小もできます。

ざっと、そんな感じです。

>環境：VC++2005Pro WinXP MFC使用 ダイアログベース
この環境なら、
CImage
がかなり楽

返信が遅くなり申し訳ありません。
みなさまアドバイスを元に目的のコーディングができました。
ありがとう御座いました。