Why on some GSM carriers SMS goes through and not others

I am on Canada's Microcell network a.k.a Fido. I can send SMS to friends in
Croatia. I cannot send through ICQ as I once was able to. I am thinking of
changing carriers and switching to Rogers AT&T. Apparently SMS to Croatia
cannot go through. I recall that I tried sending one using a TDMA phone. I
dont know if GSM is any different, but I presume it can't go through. Rogers
says they don't know.

Can someone explain?

Thanks