Creating a separate subsite per department should work fine, with each having its own forum package mounted underneath.
Who creates these departments dynamically? You? If so, it's not that hard to just do this manually via the site map.
If you want a push-one-button approach to adding new departments then you'll have to do some scripting on your own.
.LRN may or may not work for you, so downloading and playing is probably your best bet.
