Bind location of empty to vertex (after shapekeys)
Well I found a solution, took me a while.
Since other people might get into this as well, here is the solution:

On the object with shapekey select a vertex, create a vertex group for it.
On the Empty use a Child-Of constraint, select the object and the new vertex group. 

Note its even possible this way to copy rotation of that vertex as well.