I know you’ve gone through what you did and what customer service has indicated already, but just in case I thought I would make sure to clarify a few things about Muse operation and your steps so far.
[B]Hard/Factory[/B] Reset on a Muse is achieved by holding the button down for about [B]15 seconds[/B]. This will be verified by the LED’s doing a [B]saw tooth[/B] animation for a few seconds and then turning off. After factory reset you will need to go back to [B]paring mode[/B], hold for [B]5 seconds[/B].
Turning off the bluetooth and clearing data under Settings -> Application Management -> Bluetooth, should [B]not[/B] be necessary.
The only thing required to [B]forget[/B] the Muse is the [B]unpair[/B] it in the bluetooth menu. Once Bluetooth is on you should see a list of [B]paired devices[/B] on an Android device. If it is showing under paired devices, than as Lola has mentioned you will want to click the [B]settings icon[/B] on the right and [B]unpair[/B] it. Before doing this it will [B]never[/B] show up in the “Search for Devices” mode. This is just the way the Android, and iOS, bluetooth UI’s work.
Again, wiping cache or Dalvik Cache should [B]not[/B] be necessary.
Just to be certain I tried to wipe cache in recovery mode and data in the bluetooth management settings and it does not clear existing pairings as Lola suggested [B]may be your issue[/B].
I believe similar behaviour may occur on OSX, your MacBook if the device is already paired. However some older OSX versions may allow you to pair again and replace the original pairing. I believe [B]10.8[/B] and earlier.
The unpairing process is [B]not your problem[/B] if you’re trying to pair to devices you have never connected to Muse. The reset may help, also rebooting your iOS device may help, but further action is [B]unnecessary[/B].
If all of this has failed or does fail it is certainly possible, however unlikely, that you have a hardware defect. Any hardware can defect, you should have a [B]6 month or more warranty[/B] on your Muse. Customer care should be willing to replace defective units for you.