I have iTunes 9.0.1 running under OS X 10.6.1 on two computers - A Mac Pro and a Mac Mini.
On the Mac-Pro, I get the expected behavior when i search directly in song lists.
Click on Music under LIBRARY
Select All (Genres) All (Artists) All (Albums) in the iTunes 8 style top browser
Click on the 'Name column' to sort songs alphabetically
Then start typing, for instance "Hall", iTunes jumps directly to the first song that starts with 'Hall', in my case "Halleluja' by Charlie Parker.
On the Mac-Mini when I replicate the above, nothing happens. It looks like the Mac does not respond at all to my typing. Searching the song using the search pane top-right works both on the Mac-Pro and the Mac Mini