The problem is there is only usually one provider who Provides Brazil DIDs to the international VoIP market, therefore you are mercy to their network. It doesn't matter who provides your DID, its generally coming from the same location.
Remember Telecoms is a pyramid selling scheme. Everyone is reselling meaning that the call is bouncing around servers all over the plance possibly resulting in a higher chance of downtime.
What you are experiencing in regards to the termination is very common in the LCR (Least Cost Routing Market) where small providers like to send the call the cheapest way. Generally speaking this results in either a) False Answering and Grey Routes. When it hits grey routes, it then a case of... is there capacity on the network?? if not it pass's a busy tone back.
What you need to do is find a provider who has a direct interconnect into Brazil. The problem is they are far few and between and will not provide to the likes of VoIP.MS.
We are looking at launching a services a bit like VoIP ms over the coming months with numbers hosted on our own allocations from the in country regulators or from number allocations of our direct tier 1 interconnects. Which for all of South America we have one interconnect, but the interconnect is the major Landline/Mobile Operator there. ***At least when i have visited Peru, Chile & Brazil*** (We are expanding to become a full Operator in Peru by 2013. However our service will not be ready for at least 5-6 months.
Does the SIP Server have to be in Florida. If I remember correctly, Ring Central has a few direct interconnects on their network into South America so you may be able to try them.
I can't recommend an alternative but we are voip.ms users ourselves and haven't seen any issues. Can you post or if you prefer pm me with some of the issues you are seeing as we were just about to expand our services with them.
If Atlanta, GA is close enough I would contact Aretta.com. I guess they recently changed their name to Cbeyond Cloud Services (yuck) but aside from disliking their new name I've been very very happy with their service.