I have a solution that is applicable in a small scale project and doesn't involve programming of any sort.
Probably someone already figured this, but I'll take my chances:
1) Create an ID on the original, damaged layer
Creating an ID attribute is simple, but so is my solution, so I'll go over it.
First, you have to open your attribute table and then go to the Field Calculator, which is a button pretty much like an abacus. There, you will be given the option to create a new field or update an existing one. On the picture above I'm creating a new one called "ID". The formula is right at the end of the picture. (Sorry for having my QGIS set up in a different language. Since the design and the formulas are exactly the same throughout the language versions, I don't think it will get in our way here.)
2) Convert the polygons to lines
This step is located on the Vector > Geometry section the the menu. Your converted shape should look like this:
Right after converting the polygons to line, you will have to do the exact opposite, which is...
3) Convert lines to polygons
The options are right next to each other. Again, let's not mind the language barrier here.
The reason you did steps 2 and 3 is because now you're sure those lines will be considered as polygons, which means they now have their own line on the Attribute Table. If you check it out, it will look like this:
The first one is ALWAYS the entire polygon (trust me, I've deleted a couple hundred lines today...) and the rest are the loose lines in the middle. You can enable editing and get ready for action. If you decide to try this, two things that you should keep in mind are: organize your table ID-wise, this way you're sure you're not missing anything and use shift to select clusters of data, just like any other program.
I'm aware this is not the crème de la crème of QGIS problem-solving, but if you're facing a situation where the tools are not working because of the invalid geometries these lines create (I even tried dissolving by the ID instead of deleting manually, but it didn't work), then this might be a way out.