As Udo said, a STUN server is not necessary. A STUN server allows a device to find its public IP address and should not be necessary for what you are trying to do. Here is a link that describes what STUN servers do: http://www.voip-info.org/wiki/view/STUN
The problem you are experiencing is usually a result of outbound routes not being configured correctly. From your post, it doesn't sound like you have your own PBX so you would likely need to contact your provider to find out why it isn't working. They should be able to help you configure things on your end or make necessary changes on their end, especially if it is a paid service. There may be settings you can adjust on your end as well, but you would need to consult the documentation of your phones or search the internet for help if your service provider can't resolve the issue. Alternately, you could try a different service provider and see if the problem persists.
...
As far as server side goes, there are many options you could go with. It would be helpful to know more specifics about your business and your target customers.
Are you going to be providing to end users a retail (vonage) type service or to enterprise and businesses?
...