Just an issue that caught me out the other day, which may or may not be your problem:
On some Linux systems (e.g. Ubuntu), if the very first time you run VIM, you run it as a super-user, then the $HOME/.viminfo file gets created with root owner and your local user does not have permissions to write to it. This explained why my VIM was not storing command history when it was all configured up correctly.
Bottom line: on a *nix system, locate your .viminfo file, and make sure you have read/write permissions on it.