Agreed, it's very common to see. In many cases you're talking about people who worked together very closely for years and are verging on as close as family. Also, in higher-level roles you often get fired due to a very specific lack of skills or a very specific weakness that wouldn't be at all applicable for another job.
Ex "this person is an amazing startup CTO but they get problematically overwhelmed when the organization gets to 100 engineers" – you would 1000% recommend that person to a 50-person startup even if they got fired from their job at a 500-person company. They might even be better at it the next time around.
It's largely engineers who don't really understand the value of a C-level person, as evidenced time and time again in the comments.
The concept you could fire someone for business reasons and later be their very good friend and recommend them for another job - sometimes an even better one than you employed them in - doesn't fit the single-input single-output mind of a lot of engineers.
While this is a common attitude in western society, it does not make sense if you zoom out. Acting morally/ethically and being successful are not mutually exclusive. But it is more difficult, and it might require a more careful assessment.
You only exist because every ancestor of yours, up to your single celled ancestor, succeeded in 'life'. To denounce success for its own sake, is, for lack of a better term, stupid.
That's exactly the point. I'm C level, but at heart, I'm a hacker and and engineer, and have been for what, 24 years now (sobering). Reflecting on this isn't a criticism (though we all know how touchy engineer-types can be) -- it's just an acknowledgment. To E-types, firing is loss of job, loss of livelihood, to C-types, it's a reposition of an asset, a reassignment of a resource to a new project. All we're doing here is acknowledging this.
Thinking about this, can you think of a great hacker who isn't C-level? Look at the most famous programmers of all time, or people who've made the most popular tools like Ruby on Rails, and they're all C-level.
While I don't follow 'great' hackers, here's some names. I haven't actually checked to see if they held C-level positions so some might have.
Yukihiro Matsumoto, Satoshi Nakamoto, Linus Torvalds, Jeff Dean, Aaron Swartz, Richard Stallman, Ken Thompson, Dennis Ritchie, Guido van Rossum, Yann LeCun, Andrej Karpathy