The different departments are not 'sites' as such so there is not problem in linking them with each other as they are not within different domains. They are more like categories with sub-categories.

I see your point about how to promote the site though. I would concentrate on link building for the home page and build up its link popularity. This way the categories i.e. subdirectories will receive llink popularity over time as it is distributed down. As the link popularity for the main page grows so will it grow for the subdirectories and you will not necessarily have to do a lot of link building for each specific category. Just make sure that the theme of each category is strong and the rankings should be strong after a period of time.