Why deselecting an already selected vertex does NOT work?
Actually, yes, you are missing something ;)

The fact is, when you select all vertices of an edge or face, you also select said edge or face (same when you select all edges of a face). In other words, selection of verts, edges and faces are linked together, so if you want to deselect vertices you must first deselect all faces and edges they belong to.

Note that selection operator(s) in editmode take care of that, using current select mode as reference (such that in vertices select mode, deselecting a vertex automatically propagates to relevant edges and faces).