Надо настраивать сложную маршрутизацию.
Пусть "дешевый и медленный провайдер" даёт Вам IP-адрес "IP1",
а "дорогой, но быстрый провайдер" даёт Вам IP-адрес "IP2",
В первую очередь надо научить программы, обращающиеся наружу, обращаться от правильного IP-адреса. Т.е. "почта" (SendMail или кто там у Вас) должен открывать соединение от IP1, а браузеры юзеров работали от IP2. От этого зависит - через какого провадера Вам пришлют ответ.
Почтовая программа должна иметь в конфиге опцию - от какого адреса открывать соединение.
Либо можно в iptables загнать трафик TCP:25 в NAT на конвертацию IP-адреса.
А юзерские программы наверняка уже настроены работать через NAT (точнее, сервер перехватывает их трафик и NATит. Тут достаточно правильно прописать IP-адрес IP2. Причём, возможно, у юзеров работают SMTP и POP3 - тогда надо изменять правила NAT, вписав туда порты 25, 110 и какие там ещё используются - на IP1.
Вроде, всё.