Last modified: 2006-06-17 00:45:15 UTC
With a default install of MediaWiki 1.6.x, any search produces a page with an extra spurious ":" e.g., the URL supplied returns... There is no page titled ":Test Search". ^ Note the ": <- colon there, which is unneeded and strange.
Short answer: The colon is needed. It'll be removed soonish in trunk per a recent discussion on wikitech-l.
This was done a little while ago.