http://bugs.winehq.org/show_bug.cgi?id=18089
--- Comment #9 from Igor Tarasov tarasov.igor@gmail.com 2009-04-19 20:27:04 --- Gotcha! Thanks goes to Mark Russinovich for his great Regmon ;)
Deleting links did not work, but regmon helped. All the magic is here:
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows\CurrentVersion\App Paths
There are folders per each application. And each such folder can have various parameters, one of which is (tada!) Path.
So, that's how Explorer does that magic :)