After some Google searches and not really coming up with anything specific, I found this link which was actually showing me the solution, although I did not know it at the time.
Android Programmatically Bluetooth Pairing
Our app is using a somewhat modified version of the official Android Bluetooth sample ported to monodroid, it can be found here BluetoothChat.
The problem showed out to be this line "tmp = device.CreateRfcommSocketToServiceRecord (MY_UUID);"
changing this to
tmp = device.CreateInsecureRfcommSocketToServiceRecord (MY_UUID);
solved the problem for 3 different devices for me.
Some more Googling gave me the apparent reason behind this. There seems to be a bug in Android 4.0.3 and 4.0.4+ that is causing the Bluetooth pairing to be forgotten.
This is documented amongst others on Bluetooth connection on Android ICS not possible.
I spent quite some time trying to figure out what was wrong with the code, being in the mindset "I must be doing something wrong" and being a bit reluctant to start the "blamegame".
I hope this might help someone else out there.
Below are a few links that I went through in my hunt for a solution, they are all one way or another corroborating my findings.
ICS can't pair BT devices without PIN
Bluetooth RFCOMM Server Socket no longer connects properly to embedded device on ICS 4.0.3