Why does < C-a> (CTRL+A) not work under gvim on windows?

This is because of mswin.vim that is sourced by the default _vimrc generated when you install vim.Just override your _vimrc with the .vimrc you are using under *nix, or delete mswin.vim.

I know I'm late to the party, but I thought I'd share the following:

nnoremap <kPlus> <C-a>nnoremap <kMinus> <C-x>

This remaps increment to the + key on the numeric keypad and decrement to the - key. It's the solution I've used in my own _vimrc file on Windows. It keeps the Windows compatibility and is easier to remember than the original Ctrl+A/Ctrl+X as well.

Vim on Windows has specialized key mappings by default to make shortcuts more "windows-y". These are specified in the $VIMRUNTIME\mswin.vim file, which is loaded via your vimrc unless you disabled it. You can edit the mswin.vim file (you may want to edit a copy instead, changing your vimrc to use your edited copy instead).

I'm not entirely sure it's a default Vim mapping, since the only reference I can find on Ctrl+A in the help file is this, which doesn't seem to do what you are referring to:

*c_CTRL-A*CTRL-A      All names that match the pattern in front of the cursor are              inserted.

so you may want to check your Linux box to see if any plugins or anything change the key mapping. (Of course, it may be that I just can't find the appropriate part of the Vim help.)