How to fix a broken recovery partition (remove it) when repairing it is not possible?
I removed my partition with

$ diskutil eraseVolume HFS+ Blank /dev/disk0s3


which created a blank space. 

I then also had to repair the disk in disk utility. Since then everything works fine.