I've noticed a few annoying things about the way Terminal in OS/X handles history.
Today I opened the file at /private/etc/bashrc_Apple_Terminal and discovered that this is all because of the way sessions are handled.
I added the following to my ~/.bash_profile to change the way history and sessions are handled in Terminal.
export HISTSIZE=100000
export HISTFILESIZE=200000
# see /private/etc/bashrc_Apple_Terminal
export SHELL_SESSION_HISTORY=0 # share a single history between term sessions
`touch ~/.bash_sessions_disable`
I don't mind disabling sessions, since I always close out all my Terminal windows when I'm done with them. But, I'm sure you can figure out your own best configuration if you read through the contents of /private/etc/bashrc_Apple_Terminal