None of them are statically linked, and we looked into that for 3.5 and it had other issues, so we went fully dynamically linked.

This is either an issue specific to your machine, or a Vista issue (we didn't get a lot of testing done on Vista).

Installing the VC 2015 redistributable from http://www.microsoft.com/en-us/download/details.aspx?id=48145 should include the files you need (as should installing Python 3.5.0 itself, but apparently that didn't work). The DLL should be under C:\Windows\System32.