Problema lokalizuota ir išspręsta. Kaip ir spėjau, Android čia visai ne 
prie ko.

Esmė:

MS kažką pribūrė su naujomis skype versijomis, jog jos pasidarė 
neatsparios DNS problemoms. Jei anksčiau Skype dėdavo skersą ant bet 
kokių bandymų jį taip užblokuoti, tai dabar DNS blokas jį išveda iš 
rikiuotės. Ir dar ne bet kaip, o taip, jog iš pažiūros jis veikia, bet 
faktiškai sutrinka komunikacija ir žinutės vaikšto randomu.

Visi, kas turite minėtą problemą (daugiau detalių ankstesniame tread'e), 
pasitikrinkite savo DNS konfigus. Niekas neturi blokuoti šių DNS:

skype.com
skype.net
live.net
live.com

Jei naudojate OpenDNS, arba nejunkite "Chat" filtro, arba surašykite 
minėtus domenus į Whitelist sąrašą.