MDAC_TYP.EXE と Jet40Sp3_Comp.exe を
http://www.microsoft.com/japan/msdn/data/download.asp
ここから取ってきてインストールするだけでした、

これを再配布して良いのか悪いのかイマイチ不明ですが、とりあえずAccessランタイム無くても解決しました。
この構成でmdbの最適化（サイズを小さくするやつ）ができるのか不明ですが、これから試してみます。