If you use Ctrl+R to execute a command using the history, then hit up-arrow, the command wasn't re-added to the top of the history. The history should contain all commands as they're executed, regardless of origin.