I just tried it again and now it works. I have no real idea why it works today, but didn't yesterday, but I'll describe what I did as precise as possible, so others might get some useful information out of it:
Yesterday (didn't work)
Activated Bluetooth on smartphone Put transmitter on strap, put strap around chest. Paired transmitter with phone. I'm not sure when I started Runkeeper ... it is kind of hard to tell if an application is running or not anyway.
Today (did work)
Made the rubber part of the strap wet. Although hardly any water stayed on it, and yesterday I was heavily sweating at least a couple of minutes after I started the process, so everything should have been nicely wet. Put strap around chest. Put transmitter on Started Bluetooth. Started Runkeeper.
It seems that the heart rate sensor/transmitter has some kind of sleep mode and needs to wake up, since it does not have any kind of external switch. Maybe because the strap was dray first and only slowly got moistened there wasn't a sudden enough change for it to get started ...
I'll accept another answer if it provides something more specific, especially a way to debug this kind of issue.