Я бы здесь использовал Gearman. Это сервер организации и распределения задач, или проще говоря сервер очереди сообщений.

Почитать про него можно, например здесь

Рабоать это будет так:
Скрипт, который иницирует отправку смс:

# Подключаемся к серверу
$client= new GearmanClient();
# Регистрируем задачу для фонового выполнения
# "sendsms" - это тип задачи
# $sms - это данные письма
$result = $client->doBackground("sendmail", serialize($sms));

На этом этапе в очередь добавится ваше смс и скрипт продолжает выполнение, и как только освободится один из отправителей (воркеров в терминалогии Gearman) оно будет доставлено.

В этом случае всю черновую работу по хранению смс в очереди, по очередности отправки возьмет на себя сторонее приложение