> On Debian it changes to visual mode.

If you put this in your .vimrc, it should allow you to paste from the system clipboard by pressing space-p:

    let g:mapleader = "\<Space>"
    nmap <leader>p "*p
    vmap <leader>p "*p

(Or use `"*p` or `"+p`, not including the backticks.)

I've always used the + register to copy or paste text in vim (if X11 is enabled). Otherwise, I'll use xclip to handle interfacing with the clipboard.

    :w !xclip -selection clipboard

or

    :r !xclip -o -selection clipboard

This has nothing to do with what distro you are using, except perhaps what termcap information it has. If vim detects that the terminal can support mouse input, then it will enable mouse features. If not, vim does not get control over mouse input and your terminal provides default mouse behavior (right-click paste). You can disable mouse features with the command ":set mouse -=a". If you're pasting into vim from a terminal, you may also be interested in the "set paste" command.

That seems unrelated to vim. Doesn't it depend on your terminal if right click will paste? Try Shift right click and see if it pastes like you expect.

This is a recent misfeature. The solution is set mouse=""

I use Vim on Debian Testing, and right-click paste works fine on Gnome Terminal and Konsole, but does visual mode like you find in Xterm or UXterm.