OK, I think I've solved this.
I've created my own GetDirectories method that can handle both "//server/share" and "//server" paths. It uses regular expressions to figure out what kind of path is given and then either calls standard System.IO.Directory.GetDirectories() method for //server/share like paths or uses the code from this CodeProject article
to enumerate shared folders on the server.
Then I've changed all the calls to System.IO.Directory.GetDirectories() and System.IO.Directory.GetFiles() methods in the CustomProvider code and everything started to work fine for me.
I have to mention, that we only intend to use FileExplorer to browse files on remote server, not sure how well my solution will work for folders moving/deleting scenarios.