There are several threads here and on Apple support about pairing issues and iPhones being stuck in "searching" mode within the bluetooth pairing screen.
I had to have my iPhone 4 replaced and when I next tried to use my Nokia headphones in bluethooth mode, the iPhone would not identify the BH-905i was even there but would identify other bluetooth devices in range.
I assumed it was a bug in the latest Apple iOS as usual. But for once it wasn't ... all I had to do was clear all pairing settings in the BH-905i :
P16 of the Nokia BH-905i user manual says:
To clear the volume and pairing settings from the headset, deactivate
Bluetooth connectivity, and press and hold the multifunction key and
the volume up key (for about 5 seconds) until the Bluetooth indicator
light starts to alternate between red and green.
and this worked for me.
Good luck !