Yes. This is how bind-map works.
[ My questions are about how it *should* work rather than how it works. ]
It adds to `evil-normal-state-local-map`,
which is a buffer local key map. It does this in response to evil-local-mode-hook, which, when evil-mode is enabled, will trigger in most buffers, and when it does, if the globalized minor mode being considered has not yet been initialized (as you mention below) then it[ In your examples, while the globalized major mode has not been initialized, it *will not* be initialized later either, AFAICT. ]
cannot simply use the mode variable to determine if it's enabled.
Another way to look at the problem: when the minor mode is enabled or disabled (which can happen at any time), which part of bind-map reacts to update `evil-normal-state-local-map`?
To be clear, I think this is a flaw in bind-map. I shared the repro before I figured out an alternative that does not have this limitation and is more in line with how evil seems to work. In other words, you may feel free to disregard this repro and proceed with closing this bug if you like. I don't know if bind-map will be updated or not, but it does seem like it's not essential for it to use to the set-explicitly internal variable.
I think you're reaching the same conclusion I had reached, indeed: the approach used currently in bind-map is flawed and works only in some/most circumstances.
Stefan