I just talked to my mentor about this topic the other week as I was curious to get his opinion. He works at a large university medical center based in the midwest and is also the director of one of the neurology fellowship programs. He told me that when they are looking for new faculty they (institution/department) won't even look at any one who does not have fellowship training (this obviously is totally institutionally dependent, so I'm not sure of other institutions policies). Most of the time they make offers to their current fellows before even looking outside the institution to fill the position. He also said that research experience and funding are important aspects when looking for new faculty. He specifically mentioned that in a tough economy, if an applicant for a faculty position has grant funding already, it makes it that much easier for them to find a position. Those without funding, not so much. Ultimately you don't need to do a fellowship to get an academic position. However it will make it that much easier. Ask current residents how much extra time they have available to get the needed research experience to submit and successfully acquire grant money before applying for an academic position. It isn't impossible, but it is very difficult. Fellowships give you the added mentoring, training, and time to do research in preparation for academic medicine. A MS/MPH/PhD can't do that in and of themselves imho.
I would also recommend looking at the faculty listings at various academic programs and see how many are fellowship trained vs. not. Also look at younger faculty across institutions to see if this answers your questions.