I think the biggest thing that brings job security is to not suck at what you do (while providing multiple, high value services to your group and hospitals), be fast, efficient, and easy to work with. I've seen my fair share anesthesiologists that either suck (slow, inefficient, can't do big cases or peds or regional and OB etc) or have significant personality issues. This problem isn't unique to anesthesiology, it's rampant throughout medicine and I think it might self select to some extent. I left my first job out of residency mainly to be closer to family and I couldn't believe the how many people (techs, RN's, surgeons, partners etc) were sad or genuinely pissed I was leaving because they say I'm easy to work with, don't yell at them and stay calm and collect when SHTF. I barely knew some of them or hadn't said more than a few sentences to them over the year. During my first year out I saw 2 seasoned partners (7-10+ years of experience, including ped fellowship) get let go for either skill or personality issues with staff. I thought it was sad that the high volume pediatric surgeon would allow me, a new grad, no fellowship and not boarded for my first 8 months, to do her neonate and peds cases but not 2 individuals in town with 7+ years of experience and pediatric fellowships. This is just my limited experience so take it with a grain of salt. I'm not trying to toot my own horn, I'm just pointing out the obvious thing I didn't see spoken about much in this thread. If you suck clinically or inter-personally, no number of fellowships will help you get a job, let alone keep the job. Think about your residency class, how many co-residents would you actually want to have as a partner or take care of your family members? 25%? 50%?
With that said, a fellowship can certainly open up doors, but I am not convinced one bit that it offers much, if any job security. We provide a service and ultimately it boils down to cost, so if someone is willing to or can do it for cheaper, they'll often times succeed even if quality takes a hit.