Another happy Amarok user here. I always fix the tags with Easytag
before adding them to the collection. With proper tags the search works
perfectly. Easytag can fetch tags from cddb also, and rename files from
tags.
If only Amarok had a replay gain function like fb2k I reckon it would be
perfect. It does take over half an hour to scan my 10000 tracks, but
hey, you only need to do that once.