Getting the error "The 'VFPOLEDB.1' provider is not registered on the local machine" even after installing and registering the provider

It is registered as it should. It is your application that is compiled for AnyCPU Platform.
In x64 operating system this produces 64bit code and 64bit code could not access 32bit drivers.

Change your Platform to x86 and you will be fine.

EDIT
Two years later there is something to add to this answer. Now with Visual Studio 2013 the cheese has been moved. The article linked explain in great details how the compiler setup defaults has been changed. The AnyCPU target CPU with Prefer 32 bit means that your application works as 32bit app also in x64bit operating systems leaving practically no-room to x64 application unless specifically required.

With this new configuration becomes also important to remember what is posted in comments below by Mark Berry. If your (now 32bit) app needs to work in a IIS 64bit environment you need to set the Application Pool with Enable 32 bit Applications

I have desktop app (Win7 x64 VS 2015) - and kept getting the same error no matter what. I changed platform target to x86, installed MSI as admin etc - did everything I could google - and no luck. What helped me is to install MSI for Everyone instead of Just me - one of the last wizard's screen in the setup.