Index: trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java	(revision 18130)
+++ trunk/src/org/openstreetmap/josm/gui/widgets/ComboBoxHistory.java	(revision 18131)
@@ -42,4 +42,5 @@
         String newEntry = o.getValue();
 
+        boolean alreadyAdded = false;
         // if history contains this object already, delete it,
         // so that it looks like a move to the top
@@ -47,10 +48,17 @@
             String oldEntry = getElementAt(i).getValue();
             if (oldEntry.equals(newEntry)) {
-                removeElementAt(i);
+                if (i == 0) {
+                    alreadyAdded = true;
+                    break;
+                } else {
+                    removeElementAt(i);
+                }
             }
         }
 
-        // insert element at the top
-        insertElementAt(o, 0);
+        if (!alreadyAdded) {
+            // insert element at the top
+            insertElementAt(o, 0);
+        }
 
         // remove an element, if the history gets too large
Index: trunk/src/org/openstreetmap/josm/gui/widgets/HistoryComboBox.java
===================================================================
--- trunk/src/org/openstreetmap/josm/gui/widgets/HistoryComboBox.java	(revision 18130)
+++ trunk/src/org/openstreetmap/josm/gui/widgets/HistoryComboBox.java	(revision 18131)
@@ -6,4 +6,5 @@
 import javax.swing.text.JTextComponent;
 
+import org.openstreetmap.josm.data.tagging.ac.AutoCompletionItem;
 import org.openstreetmap.josm.gui.tagging.ac.AutoCompletingComboBox;
 import org.openstreetmap.josm.spi.preferences.Config;
@@ -55,5 +56,11 @@
      */
     public void addCurrentItemToHistory() {
-        model.addElement(getEditor().getItem().toString());
+        Object item = getEditor().getItem();
+        // This avoids instantiating multiple AutoCompletionItems
+        if (item instanceof AutoCompletionItem) {
+            model.addElement((AutoCompletionItem) item);
+        } else {
+            model.addElement(item.toString());
+        }
     }