El centrado vertical en la opciones de un menú hecho con listas (ul/li/a) suele lograrse con las propiedades line-height o el padding superior e inferior.
El centrado horizontal dependerá de las particularidades de cada situación, principalmente de si se conocen a priori o no el nº de opciones, si se quiere dar una anchura igual a todas las opciones o estará en función de su contenido, etc.
Una de las últimas realizaciones contemplando alguna particularidades muy concretas fue
ésta.
Como verá no hace uso ni del display:inline-block ni de tabe/table-cell y otras habituales para hacerlo compatible con los ie.
Quizás le sirva como base para sus necesidades.