Why not? Outside of his last season in Pittsburgh, which I believe was cut short with injuries/concussion, Fleury's best stretch of years in Pittsburgh were literally 3 of his last 4 years there. Fleury's a rare example of a goaltender that's been better in his 30's than he was in his 20's.
I never considered Fleury better than average between 2003-2013. He had some good years, but he also had mediocre ones. I always considered him an average goalie on a stacked team up until about 4 years ago.
Not every goalie plays worse because of the team, like you seem to believe. Of course there are guys like Brian Elliott, who never look good without Hitchcock, but there's plenty of teams that have two goalies that are not playing to the same level. Just look at the difference between DeSmith and Murray this year in Pittsburgh behind the same team.
Because they saw him as too unreliable come playoff time and they had a cheaper option in the wings. Fleury has had complacency issues in Pittsburgh as well. They would've felt like it was time to move on regardless.