WEBIVAN

Я бы поискал как минимум 3 шлюза, один на СНГ, второй на европу, третий на Америку.
Если использовать 1 шлюз, обычно получаем низкие цены на один, из указанных выше регионов и переплату в 1,5-3 раза на остальные

Пользуюсь smsbill.com.ua более года. Проблем пока не было.

smsbill.com.ua/
Юзаю на одном своем проекте, % от стоимости по Украине на момент подключения был самым вкусным. Работает стабильно, подключается без проблем.

По сути вам необходимо 2 услуги «Рассылка смс» и «Входящий номер для смс».
Как в России не скажу, а в Украине запрещена отправка смс от цифровых отправителей, возможно в России также. А если это так, значит ответить банально через функцию «ответ» не получится. Хотя можно попробовать извратиться с отправителем типа abc4444, в этом случае большинство телефонов при ответе отправит смс на 4444

Кстати я тут подумал, наверное в идеале стоит банить не номер или Альфа-имя отправителя, а пару номер(альфа-имя)-номер смс центра.
Поскольку реальная смс от beeline будет оправлена через sms центр Билайна, а фейковая через «левый» смс центр.
P.S. Не знаю можно ли получить смс-центр отправителя в андроид, но в старых нокиях такая инфа показывалась, а значит получить ее возможно.

У компании которой я пользуюсь, SMS, Sms и sms это 3 разных отправителя и каждого из них утверждать требуется отдельно. А вот учитывает ли регистр Android — не скажу.
Может стоит отправить 2 смс от отдного отправителя в разном регистре, и дальше тестить прогу на них?

p.s.: и наверное, оффтоп-вопрос, каким образом работают смс-шлюзы — не могут же они каждый полученный запрос сразу же отправлять оператору smpp-протоколом, или я ошибаюсь?

Ну почему же, не вижу никаких проблем в мгновенной отправке по smpp.

По поводу реализации, не вижу зачем тут использовать базу вообще. Запускаете демон на php, который слушает произвольный порт. На этот же порт отправляете сообщения и ставите их в очередь внутри самого php(скажем в массив), как только количество сообщений достигает нужного количества — отправляете их.
В идеальном варианте вам понадобится libevent что бы не дергать сокеты в вечном цикле и pcntl для форков, дабы не вызывать фоновые задания через exec и прочие.