Thank you for all the answers!
As Thomas, I suspect these problems to be timing-related as well, but according to Audric, it is fixed-step logic, meaning it should behave exactly the same on both slow and fast computers.
Firstly I checked all the variables that could cause problems when left uninitialized and initialized them. I also fixed some bugs in the code, check the commit history on Bitbucket for more info.
The game is very inconsistent now - sometimes it works like it's supposed to, sometimes all the originally mentioned bugs come back (except for the choppiness, which could very well be due to running the OS in VirtualBox as Thomas mentioned). I do have to add though that the "stuck keys" problem seems to be reduced only to the spacebar now, no other controls go rogue besides that one.
There's a bug in the game that I haven't mentioned that happens every time you quit by hitting ESC on Linux:
*** Error in `./blasteroids': double free or corruption (!prev): 0x0978d7a8 ***
Aborted (core dumped)
I tried tracking it down with Valgind and GDB, but didn't succeed with either. It only pops up after hitting ESC, so it probably has to do something with the shutdown() function, although I didn't find anything in there that would cause it.
Another bug I noticed that I didn't include in the original post is that the current score seems to overflow after hitting a few asteroids, resulting in displaying a huge score suddenly that doesn't return back to its original state.
I decided to upload the Linux executable, so you don't have to go through the hassle of building the game yourself if you want to debug/run tests/etc. Debug information is included courtesy of the -g flag, look for it in the attachment.