Index: src/org/openstreetmap/josm/gui/dialogs/PropertiesDialog.java
===================================================================
--- src/org/openstreetmap/josm/gui/dialogs/PropertiesDialog.java	(revision 271)
+++ src/org/openstreetmap/josm/gui/dialogs/PropertiesDialog.java	(revision 272)
@@ -12,4 +12,6 @@
 import java.awt.event.ActionEvent;
 import java.awt.event.ActionListener;
+import java.awt.event.FocusAdapter;
+import java.awt.event.FocusEvent;
 import java.awt.event.KeyEvent;
 import java.awt.event.MouseAdapter;
@@ -37,4 +39,5 @@
 import javax.swing.table.DefaultTableCellRenderer;
 import javax.swing.table.DefaultTableModel;
+import javax.swing.text.JTextComponent;
 
 import org.openstreetmap.josm.Main;
@@ -48,4 +51,5 @@
 import org.openstreetmap.josm.gui.annotation.ForwardActionListener;
 import org.openstreetmap.josm.gui.preferences.AnnotationPresetPreference;
+import org.openstreetmap.josm.tools.AutoCompleteComboBox;
 import org.openstreetmap.josm.tools.GBC;
 import org.openstreetmap.josm.tools.ImageProvider;
@@ -165,6 +169,6 @@
 
 	/**
-	 * Open the add selection dialog and add a new key/value to the table (and to the
-	 * dataset, of course).
+	 * Open the add selection dialog and add a new key/value to the table (and
+	 * to the dataset, of course).
 	 */
 	void add() {
@@ -193,6 +197,8 @@
 		for (int i = 0; i < data.getRowCount(); ++i)
 			allData.remove(data.getValueAt(i, 0));
-		final JComboBox keys = new JComboBox(new Vector<String>(allData.keySet()));
+		final AutoCompleteComboBox keys = new AutoCompleteComboBox();
+		keys.setPossibleItems(allData.keySet());
 		keys.setEditable(true);
+		
 		p.add(keys, BorderLayout.CENTER);
 
@@ -200,24 +206,22 @@
 		p.add(p2, BorderLayout.SOUTH);
 		p2.add(new JLabel(tr("Please select a value")), BorderLayout.NORTH);
-		final JComboBox values = new JComboBox();
+		final AutoCompleteComboBox values = new AutoCompleteComboBox();
 		values.setEditable(true);
 		p2.add(values, BorderLayout.CENTER);
-		
-		ActionListener link = new ActionListener() {
-
-			public void actionPerformed(ActionEvent e) {
-				String key = keys.getEditor().getItem().toString();
-				if (allData.containsKey(key)) {
-					Vector<String> newValues = new Vector<String>(allData.get(key));
-					Object oldValue = values.getSelectedItem();
-					values.setModel(new DefaultComboBoxModel(newValues));
-					values.setSelectedItem(oldValue);
-					values.getEditor().selectAll();
+	    
+		// get the combo box' editor component
+		JTextComponent editor = (JTextComponent) values.getEditor().getEditorComponent();
+		// Refresh the values model when focus is gained 
+		editor.addFocusListener(new FocusAdapter() {
+            public void focusGained(FocusEvent e) {
+            	String key = keys.getEditor().getItem().toString();
+            	if (allData.containsKey(key)) {
+					values.setPossibleItems(allData.get(key));
+				} else {
+					values.removeAllItems();
 				}
             }
-			
-		};
-		keys.addActionListener(link);
-		
+        });
+
 		JOptionPane pane = new JOptionPane(p, JOptionPane.PLAIN_MESSAGE, JOptionPane.OK_CANCEL_OPTION){
 			@Override public void selectInitialValue() {
Index: src/org/openstreetmap/josm/tools/AutoCompleteComboBox.java
===================================================================
--- src/org/openstreetmap/josm/tools/AutoCompleteComboBox.java	(revision 272)
+++ src/org/openstreetmap/josm/tools/AutoCompleteComboBox.java	(revision 272)
@@ -0,0 +1,90 @@
+package org.openstreetmap.josm.tools;
+
+import java.util.Collection;
+
+import javax.swing.ComboBoxModel;
+import javax.swing.DefaultComboBoxModel;
+import javax.swing.JComboBox;
+import javax.swing.text.AttributeSet;
+import javax.swing.text.BadLocationException;
+import javax.swing.text.JTextComponent;
+import javax.swing.text.PlainDocument;
+
+/**
+ * @author guilhem.bonnefille@gmail.com
+ */
+public class AutoCompleteComboBox extends JComboBox {
+
+	/**
+	 * Auto-complete a JComboBox.
+	 * 
+	 * Inspired by http://www.orbital-computer.de/JComboBox/
+	 */
+	private class AutoCompleteComboBoxDocument extends PlainDocument {
+		private JComboBox comboBox;
+		private boolean selecting = false;
+
+		public AutoCompleteComboBoxDocument(final JComboBox comboBox) {
+			this.comboBox = comboBox;
+		}
+
+		public void remove(int offs, int len) throws BadLocationException {
+			if (selecting)
+				return;
+			super.remove(offs, len);
+		}
+
+		public void insertString(int offs, String str, AttributeSet a) throws BadLocationException {
+			super.insertString(offs, str, a);
+
+			// return immediately when selecting an item
+			// Nota: this is done after calling super method because we need
+			// ActionListener informed
+			if (selecting)
+				return;
+
+			// lookup and select a matching item
+			Object item = lookupItem(getText(0, getLength()));
+			if (item != null) {
+				// remove all text and insert the completed string
+				super.remove(0, getLength());
+				super.insertString(0, item.toString(), a);
+				// select the completed part
+				JTextComponent editor = (JTextComponent)comboBox.getEditor().getEditorComponent();
+				editor.setSelectionStart(offs + str.length());
+				editor.setSelectionEnd(getLength());
+			}
+			setSelectedItem(item);
+		}
+
+		private void setSelectedItem(Object item) {
+			selecting = true;
+			comboBox.setSelectedItem(item);
+			selecting = false;
+		}
+
+		private Object lookupItem(String pattern) {
+			ComboBoxModel model = comboBox.getModel();
+			for (int i = 0, n = model.getSize(); i < n; i++) {
+				Object currentItem = model.getElementAt(i);
+				if (currentItem.toString().startsWith(pattern))
+					return currentItem;
+			}
+			return null;
+		}
+	}
+
+	public AutoCompleteComboBox() {
+		JTextComponent editor = (JTextComponent) this.getEditor().getEditorComponent();
+		editor.setDocument(new AutoCompleteComboBoxDocument(this));
+	}
+
+	public void setPossibleItems(Collection<String> elems) {
+		Object oldValue = this.getSelectedItem();
+		DefaultComboBoxModel model = (DefaultComboBoxModel)this.getModel();
+		model.removeAllElements();
+		for (String elem : elems) model.addElement(elem);
+		this.setSelectedItem(oldValue);
+		this.getEditor().selectAll();
+	}
+}