As bookcasey said, height: 100%;
will only make the DIV 100% of its parent. For this reason you will need to make html, body {height: 100%; min-height: 100%}
as stated by Marko, but also, make the same change on every parent DIV of #menu
.
Because you have a bottom border, then apply the right border to the parent DIV at height: 100%;
and apply the bottom-border to your #menu
at whatever height you want the bottom border to show up.