I can't even deselect vertices with rectangular selection tool. Dunno if it is originally like that
Yes, that is standard behavior. AFAIK there is no modifier key (shift, alt, whatever) that will make it subtract from, instead of adding to, the selection. What does work, however, is to invert the selection (so that all vertices that were not selected are now selected, and vice versa), select the vertices you want to deselect, and invert the selection again.