Bill was sure struggling in 2000 and early 2001 before Tom took over. That roster was stripped down and was a poor fit for Bledsoe. Sound familiar? His play suffered and Bill's defenses weren't good enough to overcome it - kind of like now. Assistant coaches were telling the media they planed on putting their homes up for sale as they were anticipating their jobs were in jeopardy. Belichick also told Herm Edwards before the Jets game something along the lines that things weren't going well in terms of job security.
He hit the lottery with Tom and his job became way easier as the years went on knowing his QB was getting better. You can see the correlation of HC's and how well their QB plays. McCarthy was in GB a long time with Favre/Rodgers, Andy Reid is now regarded as the best in the game because of Mahomes, Harbaugh has new life with Lamar Jackson, Tomlin had Rothlesburger, and the list goes on. When the HC doesn't have good QB play/can't draft, they eventually get canned.