Index: src/Core/Banshee.Services/Banshee.Database/BansheeDbFormatMigrator.cs
===================================================================
--- src/Core/Banshee.Services/Banshee.Database/BansheeDbFormatMigrator.cs	(revision 5150)
+++ src/Core/Banshee.Services/Banshee.Database/BansheeDbFormatMigrator.cs	(working copy)
@@ -52,7 +52,7 @@
         // NOTE: Whenever there is a change in ANY of the database schema,
         //       this version MUST be incremented and a migration method
         //       MUST be supplied to match the new version number
-        protected const int CURRENT_VERSION = 27;
+        protected const int CURRENT_VERSION = 28;
         protected const int CURRENT_METADATA_VERSION = 5;
         
 #region Migration Driver
@@ -643,6 +643,24 @@
         
 #endregion
 
+#region Version 28
+
+        [DatabaseVersion (28)]
+        private bool Migrate_28 ()
+        {
+            // Update search keys for new space-stripping behavior.
+            connection.Execute ("UPDATE CoreArtists SET NameLowered = HYENA_SEARCH_KEY(IFNULL(Name, ?))",
+                                ArtistInfo.UnknownArtistName);
+            connection.Execute ("UPDATE CoreAlbums SET ArtistNameLowered = HYENA_SEARCH_KEY(IFNULL(ArtistName, ?))" +
+                                "                      TitleLowered = HYENA_SEARCH_KEY(IFNULL(Title, ?))",
+                                ArtistInfo.UnknownArtistName, AlbumInfo.UnknownAlbumTitle);
+            connection.Execute ("UPDATE CoreTracks SET TitleLowered = HYENA_SEARCH_KEY(IFNULL(Title, ?))",
+                                TrackInfo.UnknownTitle);
+            return true;
+        }
+
+#endregion
+
 #pragma warning restore 0169
         
 #region Fresh database setup
Index: src/Libraries/Hyena/Hyena/Tests/StringUtilTests.cs
===================================================================
--- src/Libraries/Hyena/Hyena/Tests/StringUtilTests.cs	(revision 5150)
+++ src/Libraries/Hyena/Hyena/Tests/StringUtilTests.cs	(working copy)
@@ -235,6 +235,19 @@
             AssertSearchKey ("?", "");
             AssertSearchKey ("/", "");
         }
+        
+        [Test] // http://bugzilla.gnome.org/show_bug.cgi?id=573484
+        public void TestCollapseSpaces ()
+        {
+            AssertSearchKey ("  a  \t  b  ", "a b");
+            AssertSearchKey ("100 % techno", "100 techno");
+            
+            // Character in the set of special overrides
+            AssertSearchKey ("a \u00f8", "a o");
+            
+            // Invalid combining character
+            AssertSearchKey ("a \u0301", "a");
+        }
     }
 
     [TestFixture]
Index: src/Libraries/Hyena/Hyena/StringUtil.cs
===================================================================
--- src/Libraries/Hyena/Hyena/StringUtil.cs	(revision 5150)
+++ src/Libraries/Hyena/Hyena/StringUtil.cs	(working copy)
@@ -171,7 +171,7 @@
             dict['\u0142'] = 'l';
             return dict;
         }
-        private static Dictionary<char, char> ignored_special_cases = BuildSpecialCases ();
+        private static Dictionary<char, char> searchkey_special_cases = BuildSpecialCases ();
         
         //  Removes accents from Latin characters, and some kinds of punctuation.
         public static string SearchKey (string val)
@@ -184,20 +184,36 @@
             StringBuilder sb = new StringBuilder ();
             UnicodeCategory category;
             bool previous_was_latin = false;
+            bool got_space = false;
             
             // Normalizing to KD splits into (base, combining) so we can check for Latin
             // characters and then strip off any NonSpacingMarks following them
-            foreach (char c in val.Normalize (NormalizationForm.FormKD)) {
+            foreach (char orig_c in val.TrimStart ().Normalize (NormalizationForm.FormKD)) {
+                
+                // Check for a special case *before* whitespace. This way, if
+                // a special case is ever added that maps to ' ' or '\t', it
+                // won't cause a run of whitespace in the result.
+                char c = orig_c;
+                if (searchkey_special_cases.ContainsKey (c)) {
+                    c = searchkey_special_cases[c];
+                }
+                
+                if (c == ' ' || c == '\t') {
+                    got_space = true;
+                    continue;
+                }
+                
                 category = Char.GetUnicodeCategory (c);
-
-                if (ignored_special_cases.ContainsKey (c)) {
-                    sb.Append (ignored_special_cases[c]);
-                } else if (category == UnicodeCategory.OtherPunctuation) {
+                if (category == UnicodeCategory.OtherPunctuation) {
                     // Skip punctuation
                 } else if (!(previous_was_latin && category == UnicodeCategory.NonSpacingMark)) {
+                    if (got_space) {
+                        sb.Append (" ");
+                        got_space = false;
+                    }
                     sb.Append (c);
                 }
-
+                
                 // Can ignore A-Z because we've already lowercased the char
                 previous_was_latin = (c >= 'a' && c <= 'z');
             }
