Ugh;

Here's what I see. Let's say I have Don1, Don2, Don3, Don4, Don5 as paladins and Don6-Don10 as shamans. I'll logout Don6-Don9 and login Don1-Don4 (using 4 pallies from that team with my lead shaman). What happens is that none of the paladins show as online to the shaman but they all show online to the other Paladins. If I login 2 shams and 3 pallies, the two shams see each other as online, the 2 pallies see each other but the shams won't see the pallies and vice versa.
I know you have done this, but I'm asking anyway... Have you checked that all 10 toons are using the same channel? If the two teams are on different channels, they will not be able to see each other.

(If the WoW channels are all messed up you might need to clear out your chat channel information in WTF / Cache, or where-ever it is stored on disk.)