Kernel panic on every attempt to access Recovery Mode
After I forgot this issue for a while I stumbled upon a very useful tool made by Chris Silvertooth. The latest version of his Recovery Partition Creator can be found on his download page.

Using the application is very simple, I have successfully recreated my recovery partition on El Capitan (OS X 10.11.6):


(Optional but recommended) Create a full backup of your system
Download the most recent Recovery Partition Creator
Download the relevant OS X installation files from the App Store


Open the App Store
Open the Purchased tab
Find the installation file of the OS you're trying to add a recovery partition to and download it

Start the Recovery Partition Creator and follow the steps described in the dialogs. At some point you will need to point it to the installation files downloaded in the previous step.