As R stated…In some places.Like South America,it is a grace zone.It is not Legal but it is not illegal.In Jamaica,it is Illegal.It all depends.You will have to research.
I believe that it depends what service is actually being provided by the vendor. Some IXC carriers are carrying a percentage of their backbone voice traffic as VOIP and I believe it would fall under same regulations as TDM traffic. Some new CLECs and cable MSOs are offering local voice services and are regulated similarly to the ILECs for the service. But if you are talking about the free/cheap voice over the Internet stuff, I believe that is viewed as being equivalent to normal Internet data traffic.
In Indonesia, for now, You can run business based VoIP. It is forbidden by Indonesia government because they have to prepare VoIP infrastructure too, so that they will not loose big money if the player in this business start their way of catching the customers
In ecuador is illegal to do Intl calls even if is VOIP, cybercafes signed an agreement with state owned telco to be able to make calls, but i just had my phone lines temporaly suspended for doing prepaid calling cards going trough VOIP.