In ido mode, C-s rotate the matches. The following steps exhibits a
delicate bug which seemingly causes the matches to re-order.

1. Emacs -q -l long-list.el (attached)
   take a look at the first 4 matches in the minibuffer
2. C-s

Normally you expect C-s to get you one step closer to the fourth item
but it just pushes it one step further in this case.

This is also reproducible with the ido.el included in Emacs 22.

It may have something to do with prefix-matches, matches, suffix-mathes
in ido-set-matches-1.

BTW, in my local copy of ido.el I have integrated recentf into it so ido
automatically pulls in visited files when switching buffers and the user
input does not match any. I have a long recentf-list.