Bonjour/NSNetServiceBrowser on the iPhone/iPod Touch will utilize both Wifi and Bluetooth for service discovery--at least on supported devices. Each time you begin browsing for services, it will search both WiFi and Bluetooth (which you can verify in the iPhone's Console, in Organizer). Since your Simulator "device" cannot use Bluetooth, your iPhone discovers it over WiFi. However, if you are using NSNetService to publish on your iPhone, then you are publishing over both WiFi and Bluetooth as well (if supported and enabled). NSNetServiceBrowser, when running on BT-capable hardware, will dutifully find that both instances, and report both via delegate callbacks.
Bluetooth PAN setup takes longer than publishing via Wifi, so the BT-discovered services often show up well after all the Wifi-based services have been discovered and resolved. When testing two real devices, I've even seen both services show up in my UI (usually only after the other phone crashes).
It does make for some frustrating coding, though. Your best bet is to utilize netService:didNotResolve: to either (i) retry resolution, or (ii) invalidate the netService instance and wait for the other phone to relaunch their app.
Also, there are a couple of other areas things can go wrong. Since the NSNetService instance provided to you is autoreleased, you need to retain it. Most people add it to an NSMutableArray or NSMutableDictionary. If that's the case, make sure that you have properly initialized it before adding the object. Since messages to nil are perfectly ok, if you send addObject: to nil it will appear as though everything is working fine. Except that it isn't. This crops up very often in Bonjour troubleshooting, and happens to the best of us. Make sure that your NSNetService gets scheduled into an actively running runloop, and one that is running in default or common modes.
There is an open bug filed with Apple (as of 10/4/09) whereby every so often, a Bonjour update will not result in a delegate method getting fired. I have only observed this occurring on a 3GS. The result is a client app that is out of sync with the network.
NSNetServiceBrowser should consistently notify when a service leaves the network (under nominal conditions). The bug above is only an intermittent one, and apparently, hardware specific. If you see it occurring consistently, then it's likely that your app is throwing an exception. If you are using background threads, this can occur without causing your whole app to crash. You may want to check your iPhones Console and logs for error messages. Make sure you have set a breakpoint on the symbol objc_exception_throw.
Here's another troubleshooting tip that I've found invaluable. Monitor Bonjour broadcasts on your dev machine via Terminal using the following command: dns-sd -B _serviceName. This will let you see all comings and goings on your local network for your service. If your app quits, but dns-sd does not show a Remove event, then your code needs revisiting. If dns-sd shows a remove event, but your other apps don't process it correctly, you may be seeing the above mentioned bug. It may also be the case that your code isn't doing what you think it's doing. And remember, this will only help you troubleshoot Wifi-to-Wifi service Bonjour. Bluetooth to Bluetooth is not supported from the iPhone Simulator.
Read the full article, Troubleshooting Bonjour Networking for the iPhone, at my dev blog.