I really don't see your problem. All that was needed here on my box was setting VIM as my editor of choice (I preferer to do that per-user so no setting of anything in rc or /etc/env.d) and VISUDO accepted it. No magic involved.
Sebastian, I already fixed the problem for my local host. But I know other users have same problem. That's strange for me that you first login as root to use visudo program. What is the matter of having sudo then? Once again, try running "sudo visudo" as unprivileged user (that's right, sudo is used to make root stuff without logging with root ;-) ) -- Best regards, Spinal