Как заблокировать выход в интернет не через прокси?

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

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

Разрешите трафик на прокси на фаерволе, и запретите весь остальной трафик.

Не только могут, но и непременно будут :) Чтобы приложение использовало прокси, оно должно либо прочитать его настройки из системы либо запросить их у админа, показав какие-нибудь окошки.
Некоторые, особо умные не умеют делать ни того ни другого. Их приходится пропускать напрямую, к сожалению.