diff --git a/src/com/android/bluetooth/btservice/RemoteDevices.java b/src/com/android/bluetooth/btservice/RemoteDevices.java
index 7d3d319..bb723a7 100644
--- a/src/com/android/bluetooth/btservice/RemoteDevices.java
+++ b/src/com/android/bluetooth/btservice/RemoteDevices.java
@@ -34,7 +34,7 @@
 import java.util.Queue;
 
 final class RemoteDevices {
-    private static final boolean DBG = true;
+    private static final boolean DBG = false;
     private static final String TAG = "BluetoothRemoteDevices";
 
     // Maximum number of device properties to remember
@@ -96,10 +96,15 @@
             prop.mAddress = address;
             String key = Utils.getAddressStringFromByte(address);
             DeviceProperties pv = mDevices.put(key, prop);
+
             if (pv == null) {
                 mDeviceQueue.offer(key);
                 if (mDeviceQueue.size() > MAX_DEVICE_QUEUE_SIZE) {
                     String deleteKey = mDeviceQueue.poll();
+                    for (BluetoothDevice device : mAdapterService.getBondedDevices()) {
+                        if (device.getAddress().equals(deleteKey)) return prop;
+                    }
+                    debugLog("Removing device " + deleteKey + " from property map");
                     mDevices.remove(deleteKey);
                 }
             }