When crontab called with -e option, it tries to execute /bin/vi (and no VISUAL/EDITOR is set as per default). But vi is in /usr/bin/vi!
vi is in /bin/vi here; it's simply using the glibc definition in paths.h.
Oh, mom! I apologize. This was really my fault -- I installed elvis instead of vi, and forgot this.