As per title, how can I add a vertical-align: middle to that one?

You don't, vertical-align is not meant for that use.
I would suggest using a background image for the <li> or the <a> and then you can position the BG image where you want it.

Yeah, that is exactly what I do. One of the problems problems with list-style: image, is that the image doesn't always line up like we imagine it should.