[El Scorpio]

Всё красиво, но как быть с клиентами которые получают адрес по DHCP? Сегодня он один, а завтра в общем виде другой. »

Указать срок аренды адресов - 1 месяц или даже 1 год.
Поскольку для используемых адресов срок аренды постоянно продляется, у всех всегда будут одинаковые адреса.

Может стоит политиками раздать адрес прокси-сервера для браузера (но опять же только для IE) »

Стоит. Поскольку в параметрах Firefox и других альтернативных программ изначально указано "использовать системные параметры прокси", никто ничего не заметит.
А на маршрутизаторе разрешить входящие/исходящие соединения только для IP прокси-сервера. Таким образом в обход прокси никто не выйдет.

Захотел человек в интернет, вылезла ему страничка авторизации, он влогинился (или по krberos вошёл) и устремился в дебри необъяной сети »

Обычный режим работы SQUID. Очень удобно настраивать через Webmin. А Firefox и другие программы вполне успешно запоминают пароли запроса прокси.
Также Squid вроде бы поддерживает авторизацию через Kerberos