I just wanted to add the below in addition to the verified answer, for a very specific scenario.
I was recently asked to fix the same problem that the OP was experiencing for a work machine, which had recently had the user accounts migrated over to a new domain.
Setup:
Visual Studio 2013
PTVS 2.2.30718
Anaconda 3.5
Basically, Anaconda was installed for localmachine/UserA.
Once the users were migrated over to the new domain (newdomain/UserA), the Python environment had to be updated from within VS2013, by clicking View > Other Windows > Python Environments.
Once that was setup, the python scripts would run as expected, although none of the Search Folder references would work. They were then removed and re-added but to no avail.
Various other things were tried, including setting up totally fresh projects, and linking them using the Search Paths, but to no avail.
The only thing that fixed the problem was to reinstall the Python Environment (in my case Anaconda3) outside of a user account (by clicking the "for all users, using administrator privileges" option during the install).
Then I restarted, removed and re-added the search folders, and the python worked as expected, including all the search paths.
I hope that helps someone, as I just wasted hours solving it...
D :)