Vertical centering of links in a menu with variable height

Question

I have a menu and a CSS as shown below and to play around also on http://codepen.io/Sofian777/pen/PqeyQa

I need to vertical align the menu items and tried all kind of things with vertical-align:middle and different display: settings on li and a (because it online works on inline elements) but I couldn't get it to work.

Anybody knows how to achieve this?

Edit: This is just a simplified scenario that I thought will be enough, but it wasn't, so here is my full scenario: http://codepen.io/Sofian777/pen/NqMOom (see short description in my comment to the answer of GolezTrol)

<div id="menu"> 
      <ul>
            <li><a href="#">Home</a></li>
            <li><a href="#">Menu Item</a></li>
            <li><a href="#">Categories</a></li>
            <li><a href="#">Contact</a></li>
      </ul>
</div> 

#menu {background: CornflowerBlue; 
  width: 100%;}

#menu ul {
    list-style-type: none; 
    text-align: center;
    height: 50px;
} 

#menu ul li {
    display: inline; 
    text-align: center;
}

#menu ul li a {
    text-decoration: none;
    display: inline-block; 
    width: 200px; 
    height: 100%;
    background: RoyalBlue;
    vertical-align: middle;
}

Answer 1

We can use the :before to help alignment.

   html, body, div, span, applet, object, iframe,
h1, h2, h3, h4, h5, h6, p, blockquote, pre,
a, abbr, acronym, address, big, cite, code,
del, dfn, em, img, ins, kbd, q, s, samp,
small, strike, strong, sub, sup, tt, var,
b, u, i, center,
dl, dt, dd, ol, ul, li,
fieldset, form, label, legend,
table, caption, tbody, tfoot, thead, tr, th, td,
article, aside, canvas, details, embed, 
figure, figcaption, footer, header, hgroup, 
menu, nav, output, ruby, section, summary,
time, mark, audio, video {
    margin:0;
    padding:0;
    border:0;
    outline:0;
    font-size:100%;
    font: inherit;
    vertical-align:baseline;
    background:transparent;
}


html {font-size:62.5%}
body {font-size: 16px; max-width: 1000px; margin: auto; line-height: 1.618;}
#menu {background: CornflowerBlue; 
  position: relative; 
  width: 100%; 
  padding-bottom: 5.6%; /* defining our 1000px : 56px ratio of the menubar */;}

#menu ul {
    position: absolute; right: 0; left: 0; top: 0; bottom: 0; /* This additional container is needed to not add the content to the padding-trick for our aspect ratio. */
    list-style-type: none; 
    text-align: center;
} 

#menu ul li {
    position: relative;
    display: inline; 
    text-align: center;
}

#menu ul li a {
    text-decoration: none;
    display: inline-block; 
    width: 20%; 
    height: 100%;
    background: RoyalBlue;
}
#menu ul li a:before{
    height: 100%;
width: 1px;
display: inline-block;
content: '';
vertical-align: middle;
}

    <div id="menu"> 
  <ul>
        <li><a href="#">Home</a></li>
        <li><a href="#">Menu Item</a></li>
        <li><a href="#">Categories</a></li>
        <li><a href="#">Contact</a></li>
   </ul>
  </div>