От прова надо потребовать 4 (или более) IP-адреса. Маршрутизатор на линухе или фре (по вкусу) с чем-то типа iproute2+nat, который каждую подсеть (по отделам) натит на свой адрес (прова), закреплённый за отделом. Доступ на виланах 802.1q, так админить легче будет, на чём-нить 48-портовом от д-линка. Но я бы с этажными делал, при таком планируемом кол-ве рабочих мест, однозначно с гбитными аплинками.
План именно такой, только я думал что железные роутеры это могут по умолчанию, а ставить на каждый отдел по настольной мыльнице типа 604 это несерьёзно.Ладно, ещё попереписываюсь с манагерами и буду поднимать "по вкусу".
А по поводу Гиговых аплинков - это никогда не поздно будет сделать. ;)