1. Можно установить все нужные пакеты в Python, который находится из реестра.
2. Можно скопировать модули как локальные для проекта (вместе со своим кодом), что бы py2exe их локально находил.
3. У py2exe есть опция includes, через которую можно указывать дополнительные модули. Предполагаю, что через sys.path у py2exe можно добавить путь для поиска.