Thanks a lot for all the info man,

Small update to any one who is thinking should it be 5 shams or 4shams + pally.
Background, I got trapped with 5sh as only team to play cause I've fucked up. I manually leveled up 4 shamans with my mage up to lvl 65 ( I'm quite good mage with ability to run SP 100+) any way, it took me like 2-3 weeks playing for 3-4 hours a day. My initial plan was to lvl up 4 toons and boost a 5th toon thus I'm not wasting too much money on it(and not getting ban).

I was thinking what 5th toon I should go with Pally or shamy (keep in mind I was consider boosting it, cause I already had 4 shamans at lvl 65 waiting to start dungeon rolling). And that's where shit started hitting fan, I realized I can't boost paly cause only playable race for paly is blood elf and blood elfs are not boost eligible. Thus I was stuck with only team 5 shamans (I was not positive to run War+4 shamans)

Long story short always go for 4sh+1p.

Long story: 5 shamans was quite hard road to be honest, leveling is ugh, and frankly speaking I consider my self quite skilled player, tho any pack in dungeon with more than 2 melee with total of 5 mobs always guarantee you either full dying or loosing a few shamans to that pack, and you need elementals for bosses thus you cant use them on trash. I'm not saying it's not possible, but from exp standpoint I was doing mana-tomb with 5 shamans at lvl 65 ( kinda okay geared with 400sp each) in around 36-40 minutes ( with flawless execution of every pull and without any room for mistakes).

After Blizzard announced fresh servers for WOTLK I've stopped gearing shamans, cause I know I'll go for a fresh and main idea behind shamans was getting ability to create a DK.
Thus I had some time to test stuff, I've moved to private server and was testing teams for WOTLK, and started leveling 4sh+p just to get to DK's and check would 4DK + P good option or not, what I can say 4shamans and pally is so much better in terms of mistake forgiveness, you can pull secondary pack and don't die insta. Clear speed is not that bad compared to 5 shamans, so I would say it's definitely a non brainier, at least from not BIS-min/maxing standpoint.
PS: any one tried WOTLK team with 5 dif classes ?