Ни "Max(X)+1", ни хранение в таблице не обеспечит уникальность, поскольку в рамках одной транзакции вы не увидите новые значения, записанные другой транзакцией (например, вашего коллеги). Поэтому для решения задачи единственным вариантом является использование надтранзакционных механизмов, а именно Sequences. Во избежание ошибок, уникальное значение из Sequence необходимо присваивать только тогда, когда документ уже сформирован, например, перед печатью документа или перед его электронным подписыванием.
Для решения проблемы "Уникальный номер отдела", придётся в БД создавать для каждого отдела свой Sequence и, например в триггере по коду отдела определять требуемый Sequence.

Кстати, для скважности и отдела, и в целом предприятия, в свое время использовал такие номера например : "123.4", где 123 - последовательность предприятия, 4 - последовательность отдела.