Hello Rob, I think the decision not to ship vim bindings happened before I was the maintainer of the package, but your suspicion is correct regarding Debian's vim not being built with python support. I don't think the bindings would work.
What I use on my machines is vim-airline, which you can install using apt or pretty much any vim plugin manager. https://tracker.debian.org/pkg/vim-airline https://github.com/vim-airline/vim-airline I don't think it can be enabled by default since vim-airline doesn't enable itself automatically. We could add vim-airline to powerline's Suggests, and mention somewhere that the bindings for vim are in that package (not sure where yet), but it's worth noting that they are two separate projects with their own codebase each (although they look pretty much the same). Thank you for reporting this, -- Samuel Henrique <samueloph>