The observation about 4.0 may be wrong, but this s evident in both the 4.0 devices I have tested : Samsung Galaxy Nexus and Samsung Nexus S. (Nexus S is actually upgraded by me to 4.0) In the other devices (HTC-Evo and ZTE-Optik), this problem is not there, compelling me to suspect 4.0 ; or Samsung as vendor.
The list of devices it is successfully able to scan have no "pattern" - it is random. It discovers the same device in one scan and may not do so the next time. Maximum 50% of the total devices in the vicinity are discovered.
EDIT : (Added more details)
The devices are close enough and the RSSI values are all > 60 dBm All the "missing" devices are getting discovered through devices < 4.0.
To add some more details, I must say the problem is not with the "other" devices - the same device shows up in one scan and fails to show in other (on Android 4.0) When I say scan - I only mean scanning through startDiscovery() in my code. If I do the scan via Device Settings, then all the devices are enlisted BUT many of them are only cached values - once I try connecting to some device, it says "Device not in range".
Any solutions ?