I understand that operators blocked any Skype over the data connections, but is there an alternative that works on the WiFi network?

Update: I am using a HTC/Tmobile G1 phone, in the US. However, I am not connected to any carrier, as I use it (here) as a PDA over WiFi and not as a phone.