Nice thought, jgbrut, but the index really isn't an option on the Reader either -- page navigation is cumbersome as there's no 'go to page' function, and the page numbers change depending on font size in the first place, so the usefulness of an index would be pretty limited.
On the other hand, most of the stuff I read (fiction) doesn't have indices in the first place, and I haven't missed the search so far.
If I got too desparate, I could always run my search in the Connect software on the PC side.