When the $company site was being designed by an agency (we did technical) I tried to disuade them from using frames but they made the navigation so large that every page would have been massive.
I now have a designer on my team and we've just relaunched the site, without frames. After 3 days google has picked up every property on the site (we have 3 mini sites text only which point to every property on the main site). These mini sites were not being picked up by google until we added a link to them from the main site. The results in google are astounding. We now come up the first page on hundreds of search combinations which we wern't even in before.
The mini sites wern't just there to drive search engines (I thought a text only version would be useful for some people, it still needs more work, pages are too large), but with the removal of frames they've really made a difference.
Moral of the story... Frames bad 'mkay!
