So I made a little progress with this. Time will tell if its actually a full resolution.
After researching further and seeing other threads (also with @LucD in them!) I started to see a common trend. Whenever New-PSDrive fails, it seems that's because the underlying PSDrive connections have been lost.
For instance, if you do a "Get-PSDrive | Select Name,Provider" in a fresh shell, you'll see something like this:
Name Provider
---- --------
A Microsoft.PowerShell.Core\FileSystem
Alias Microsoft.PowerShell.Core\Alias
C Microsoft.PowerShell.Core\FileSystem
Cert Microsoft.PowerShell.Security\Certificate
D Microsoft.PowerShell.Core\FileSystem
E Microsoft.PowerShell.Core\FileSystem
Env Microsoft.PowerShell.Core\Environment
F Microsoft.PowerShell.Core\FileSystem
Function Microsoft.PowerShell.Core\Function
G Microsoft.PowerShell.Core\FileSystem
HKCU Microsoft.PowerShell.Core\Registry
HKLM Microsoft.PowerShell.Core\Registry
Variable Microsoft.PowerShell.Core\Variable
WSMan Microsoft.WSMan.Management\WSMan
However, if you run the same command immediately after a Connect-VIServer, your output will look something like this
Name Provider
---- --------
A Microsoft.PowerShell.Core\FileSystem
Alias Microsoft.PowerShell.Core\Alias
C Microsoft.PowerShell.Core\FileSystem
Cert Microsoft.PowerShell.Security\Certificate
D Microsoft.PowerShell.Core\FileSystem
E Microsoft.PowerShell.Core\FileSystem
Env Microsoft.PowerShell.Core\Environment
F Microsoft.PowerShell.Core\FileSystem
Function Microsoft.PowerShell.Core\Function
G Microsoft.PowerShell.Core\FileSystem
HKCU Microsoft.PowerShell.Core\Registry
HKLM Microsoft.PowerShell.Core\Registry
Variable Microsoft.PowerShell.Core\Variable
vi VMware.VimAutomation.Core\VimInventory
vis VMware.VimAutomation.Core\VimInventory
vmstore VMware.VimAutomation.Core\VimDatastore
vmstores VMware.VimAutomation.Core\VimDatastore
WSMan Microsoft.WSMan.Management\WSMan
Note the vmstore/vmstores that are now present.
When I managed to replicate the New-PSDrive error, after some playing around I discovered that in that shell, the two VimInventory and VimDatastore PSDrives were lost. No clue how. Rerunning your script in that shell does not fix the issue, only closing and relaunching the a new shell did, because you were starting over and the Connect-ViServer in the new shell reestablished the drives.
So I tried running a Connect-ViServer again in the 'broken shell' but that did not correct the problem. So I went further back and discovered that running these two lines of code restore the four missing PSDrives.
Remove-Module VMware.VimAutomation.Core -force -confirm:$false
Import-Module VMware.VimAutomation.Core
So right now, anytime I am attempt to run New-PSDrive with a provider of vimDatastore in my script, I run the above two lines first. It doesn't seem to break anything else, and there is no need to run Connect-ViServer again.
I haven't encountered the error since but time will tell if that's just luck or if this is a valid workaround. This fix also seems to correct the issues I saw in parallel threads where users were getting errors to the effect of 'vmstores' being missing, or where you are attempting to use the vmstore/vmstores directly rather than using a New-PSDrive. Thats actually an elegant mode of use too, as long as you know (or discover) which vSphere Datacenter the datastore is in.
Anyhow, hope this helps someone else facing the same issue.
