Найти совместимую с нужными ОС библиотеку.
Сделать инсталлятор.
Предупреждать заранее, в каких ОС прога не работает.
Поставлять прогу в виде образа эмулятора с установленной linux+wine.
Перейти на web.
Перейти на современные платформы.
Переписать всё с нуля без библиотеки.

Клевер,

Норм советы, что тебя не устраивает-то?
Библиотеки это же не просто там, записал в папочку что ни попадя и как попало, и на тебе, будет работать.
Вот тут написано как включить в дистрибутив msxml, например.
http://msdn.microsoft.com/en-us/library/ms755709(v=vs.85).aspx

вот ещё http://support.microsoft.com/kb/278674
Целый екзешник, запускаешь его и он пишет тебе, какая версия msxml установлена. Дальше отталкиваясь от этого можно написать bat с какими-то действиями, зависящими от результата.

Если речь о каких-то других dll, регистрируемых через regsvr, то можно выяснить что они делают при регистрации и как-то поискать в реестре, установлены ли они уже.

Или, самое простое средство (если "прога" конечно тобой написана) - добавить в прогу или написать вторую прогу, которая выясняет, всё ли хорошо с dll (пробует создать объекты, перехватывает эксепшены и т.д.)