Yo uso WebSms con el conector Betamax y crédito comprado en Jumblo.com , que para Uruguay es el más económico, y te aseguro que todos los SMS llegan perfectamente. Igual te estás equivocando al ponerle (o no ponerle) el prefijo internacional (0034 o +34 para España), prueba de las 2 formas o prueba a no ponerlo.
Aquí hay una tabla de comparación con los precios de llamadas de todos los Betamax:
http://backsla.sh/betamax