авиапочтой быстрее :)
все наши провайдеры обмениваются трафиком через т.н. точки обмена IP-трафиком . Самый быстрый хостинг для России достигается установкой оборудования в тех же зданиях на тех же этажах, так что Москва не самый худший выбор. Посмотрите, откуда ваш провайдер питается и оцените маршруты самых медленных сообщений, посмотрите tracert от своего сервера до доменов клиента. На самом деле, что в Уфе сервер, что в Москве, клиент отправляет сообщение через SMTP своего провайдера (ну или свой), тот соединяется с вашим напрямую, через n-е количество интерфейсов самых разных маршрутизаторов, и маршрут скорее всего идет через эти точки, в том числе. Скорость определяется на транспортном уровне, скорее всего на вашей "последней миле" она самая медленная.