The VirtualPathNativeProvider is indeed using Microsoft Indexing Service, but it is confirmed to be not working in CMS 6 R2 (see http://world.episerver.com/Support/Bug-List/#bug,EPiServer%20CMS,74385,%2b4d5gb25szlPurXylr9TFRIdi%2fs%3d). Or rather, the indexing may work but the search function in Epi does not make use of it. I don't know what CMS version you are running?
The EPiServer Indexing Service is used only if you are working with the default VirtualPathVersioningProvider.
In our case, a migrated 4.62 site we first chose go down the Native path - in order to save some time during migration, but in the end it was a problem since search wasn't working. So next time we run the migration we configured it for the VersioningProvider and it worked!