Изменить правило на вот такое:
#menu a {
color: #fff;
display: inline-block;
height: 40px;
line-height: 40px;
padding: 0 25px;
}
Потому что высота блока ссылки у вас зависит сейчас от высоты шрифта, как ее интерпретирует browser.
vertical-align при этом не нужен, потому что указано значение line-height