At this point, I noticed once more how dependent I have become on my phone. Losing all my contacts, calendar entries and other data I entrusted my phone with: Most frightening!
After rebooting, the phone tried to connect to my webOS account. Fortunately, this connection worked as expected, and I was able to bootstrap the recovery process.
The first major hurdle was that I had to reinstall HP's root certificate patch on the phone. (The tricky part is that I had to change the date to July 1st 2013 before the patch could be installed.)
After this, most recovery steps went fine, but then trying to sync my contacts and calendar with my Gmail account, I got nothing but "unknown error" messages. It took me a while to find this gem of an article: "ALERT: Google account sync broken on webOS devices (and a fix)"
It turns out that Google started to redirect contact requests to https a while ago, and a patch needs to be installed on webOS devives to accommodate for this change.
The rough sequence of installation steps was: