Как вариант выход в Инет через прокси-сервера обоих каналов не подойдет?
Удобно тем, что не нужно заморачиваться с маршрутизацией, а доступ к тому или иному каналу обеспечивается по пользователю.

Т.е. можно было бы поставить на обоих серверах прокси с анализаторами логов - на винде - MS ISA, а на линухе - squid с sarg (или sams или lightsquid) с kerberos-авторизацией из AD (или если нет AD завести юзеров и раздать пароли юзверям если авторизация по ncsa). Если нет AD с групповыми политиками, то на общем сетевом ресурсе создать 2 reg-файлика с параметрами каждого прокси, которые активировать в startup-cкриптах пользователей в зависимости от того через какой путь он будет ходить в Инет.