After wasting two weeks on this, now they confirm that a named Firestore database is not supported with Storage rules. Seems like it's a known issue, and it's nowhere in the docs!

Firebase Support Initial response:

From what I see at the moment I’m not entirely sure to say that only default databases can be used in such a situation. Given that you specify the full path in firestore.exists(/databases/(default)/documents/users/$(uid));, I'd expect that you can replace (default) with the database ID that you want to access. If you can't get that to work, we need to check it with a minimal repro.

Firebase Support final response:

In the end it turned out that at the moment Firestore non-default database is indeed not supported. I hope this will change soon, because we have more people with a similar problem like yours.