Problem disappears when the game has good frame rate (50-60fps), again, this is on virtualized Ubuntu so this might also be related to that. I tested the game earlier on friend's Linux computer, and it run without problems.
SynchronizeWithVerticalRetrace and IsFixedTimeStep are both true, and game targets 60fps.
I press key, game has short delay before moving Player based on the input, and when I release it keeps moving the Player for a random time, but the Input after that is seen as repeatedly pressing the buttons.
As far as I know, XNA (and so MonoGame) handles low framerate by calling Update multiple times while skipping Draw to save time, so it might or might not be related to that.
It is weird, but I don't think that it is a problem as long as frame rate is consistent.