I can’t recall encountering a system in the last 15 years that didn’t have vim (or at least vi for esoteric things) on it.
I had to laugh out loud. I couldn't imagine such a system, that wouldn't be POSIX compliant. So I looked it up, and indeed, it's entirely possible. Debian doesn't necessarily include it.
I've been on a lot of systems and can't remember a single instance of not having vi (though I do vim). So pretty rare, like you said