nllm

Я выяснил, что это связано с тем, что API сервер не получает header 200 OK и считает, что сообщение не доставлено.

Тут речь скорее не про отправку идет, а про вебхук.

При отправке никаких хедеров не надо добавлять. Делаете post или get запрос с данными и все.
Вот самый простой способ отправки:

file_get_contents("https://api.telegram.org/bot***/sendMessage?chat_id=***&text=Проврека");

В первую очередь, ищите ошибку у себя в коде, где вызывается метод отправки сообщения.

Все верно расписали. Ничего сложного и извращенного нет.

На самом деле, все есть вот здесь (при условии, что группа ваша):
https://vk.com/dev/callback_api

Получаете запросы о событиях на ваш сервер. Далее делаете пересылку в телеграм.

Подобных вопросов было много:
Конечный автомат, как реализовать с циклом for при использовании telegram api?
Как написать автомат состояний (api telegram)?
Какой стандартный алгоритм работы бота?
Как сделать так, чтобы бот не потерял «нить разговора»?
Как осуществить некое подобие сессии с пользователем при использовании Телеграм бота?
и т.д.

В силу маленького опыта, не могу найти в документации

Состояния это не задача api платформы. Это задача, которую надо решать при создании бота. Поэтому и не нашли в документации ничего.

Покажите весь код.

С помощью крона каждые 24 запускайте скрипт

Похоже что падает из-за кодировки. Приходит запрос от пользователя, где имя, фамилия в кириллице.

На 99% проблема в коде, а не на сторонних сервисах (хостинг, телеграм)

Самый простой вариант.
В базу писать дату, время, id пользователя и текст сообщения. Для каждого сообщения существует статус: новое, отправка, отправлено.

С помощью крона запускать скрипт каждую минуту (или другой период времени). При запуске смотреть каким пользователям уже можно/пора отправлять сообщения.
Если уже пора, то делаем отметку в базе "идет отправка" и начинаем отправлять сообщения.
После отправки пишем в базу "отправлено".

Вроде как не сделать. Только явно отправлять (прикрепление координат или через кнопку для отправки координат)