Yes, they do.
I think some of them may have a level cap.
Thanks, i think your right about the level cap. That would explain why the early bosses stay easy when your above the expected level.
I remember Diablo get's pretty hardcore if you get high up before you verse him.
--- UPDATE ---
Just thought i would update this for anyone who's interested, I just did some testing and found out that the bosses are limited to the level of a particular character.
In the case of the test Evorite & Black Widow were both limited to the level of Zell, rather than Squals level.
Test One:
Squals lvl: 19
Zell: 9
Selphie: 8
Bosses: 9
Test Two:
Squal lvl:19
Zell: 11
Selphie: 10
Bosses: 11
Outside in the world map monsters are generally the average of the whole party. In this case about 16.