Vertical-align funkar varken mot ul eller li (bara inom "inline boxes, inom line-height på rader och inom tabellceller) om man tolkar standard "rätt" (vilket alltså inte MSIE verkar göra i detta fall).
Du får nog ta till en tabell istället för en lista om du vill ha punkterna centrerade gentemot respektive listpunkts innehåll.
Olika webbläsare använder olika kombinationer av margin och padding för att "få till" defaultvärden på indrag och mellanrum... Testa med att nolla bägge för både ul och li innan du experimenterar med indrag och radavstånd.
Sedan finns det olika webbläsaregenskaper och buggar som gör att marginaler (top och bottom speciellt) inte alltid hamnar där man vill ha dem när man har dem på element som liger inuti andra element...
Testa om det blir det bättre om du använder paddding-bottom för ditt bottebmellanrum... Blir det inte det, får du nog ge oss en länk till *hela* din kod ;)