This is all that's happening. My laptop, my other mobile and my desktop computer all see each other. But my iPhone just keeps "searching".
Any tips on what to try?
Without a jailbreak, iPhone Bluetooth only supports headsets and wireless tethering. Developers can also use the Bluetooth API to allow apps to communicate but this has limited functionality. So basically your iPhone won't discover your phone, laptop (unless it's a MacBook) or desktop because it's not designed to do so. With the MacBook, it appears that the only functionality allowed is data tethering and no file transfers or other features are enabled.
Theres a possibility that the last time a firmware was applied, it mucked the bluetooth part. I would suggest a redo from iTunes.
Also, you might want to download the iPhone Configuration Utility so that you can peek into the system logs. Might be a chance theres a log stating why it cant work.
From personal experience, sometimes, certain apps can muck somethings too. I've done these two actions.
(1-tedious but data safe) remove suspected apps one by one from the device and retrying the BT search again in between apps removal.
(2-knee jerk & data erased, pls avoid if you really cant part with your data/contacts) backup the device (backup at itunes, backup contacts to sync-able services like yahoo or ms exchange, backup pics and other data to computer), then restore firmware/factory defaults. without restoring your data, test the bluetooth - see if it works.
If it does, theres something on your previous setup that is causing it not to work (can be app, or data). Install apps and data one by one and testing BT in between installs to identify which apps is the culprit. Also, you need to recreate/copy/restore/resync your contacts and other data from scratch (not from itunes as it will only bring back the problem again)