Forum Moderators: open
IMO, it's not so much that search engines don't like frames but rather than framed website are noticeably difficult to crawl (the navigation effectively being on a different page).
Additionaly, the fact that framed sites don't appear probably means that they represent a fewer percentage of sites than 10 years ago.
It drives me crazy when sites try to keep things in front of me with frames and/or moving nav boxes that follow me down the page. Plus there are the SEO isses already noted. You can link framed info pages but that's a lame way to try and keep all content indexed most of the time. And what searchers want to land on those pages anyway.
The most tried and true method is simple, it works, and it's familar to users: Shorter pages and/or links back to the top of page. Common solutions are often also the most effective solutions.