Where did all the breadcrumbs go?

I was talking with a fellow designer this morning. He's just discovered the wonderful world of Steve Krug and "Don't Make Me Think" and mentioned breadcrumbs.

"Steve Krug said about.com do it best but I can't actually see them anywhere on the site."

He was absolutely right. They're gone. Things have changed since 2005.

I think breadcrumbs have lost most of their power since the Internet moved on to new paradigms of search and specificity.

And most sites that had them are now so enormous and multi-faceted that they're just impossible to implement. As soon as you're basing your architecture on tags or semantics instead of a fixed tree structure, breadcrumbs become crumble. When you can access any single piece of information through multiple routes, you can no longer assign it a single fixed home in a tree structure.

What do you think? Are breadcrumbs dead? And what are we using to orient our users instead?