1) I think the upgrade will work on at least some of the older iPods.
2) My understanding of the search feature is that a small letter appears on the screen when you scroll fast so you know where you are in the alphabet. Is this the "small letter" your talking about? I think that is the "search feature."
may be i am confused but the search function is from the software update, right? the updated of 5G iPOD is just bigger hdd and brighter screen, no reason why the search function cannot be function with REV.A 5G iPOD right? is a software not a hardware function.
It appears that two new interface features have been added to the ipod.
The letter that appears when scrolling to indicate where you are alphabetically seems to be available on the 5g ipods via software update (now part of itunes)
The search feature that allows you to enter letters with the click wheel and find songs seems to have been reserved for the newest (5.1g or whatever) ipods. Apple could have probably handed this out as a software update as well but im guessing they just chose not to so the newer iPod is a bigger upgrade.