You can easily partition a single site so that departments can edit only their own node of the tree using roles. You would basically create the first top level page for each department and a a role(s) for each department. You would then set the role to have edit and create child page permissions on the top level node. Now users in that role can edit the page and create additional pages below that page. This solution bypasses the need for cross site search altogether.
What you need to understand about the search index in mojoportal is its not like google. google crawls content and indexes it for search and they have no security considerations to deal with, if its crawlable then its searchable by any user. In mojoPortal, the search index is mainatained as content is created and updated and the roles that can view the indexed content are stored and kept in sync in the search index itself. When a user searches within a mojoportal site, he only sees search results for content that he has permission to view based on his roles in the site and the roles allowed to view the content. Now if all of your content is meant to be publicly viewable then maybe this feature is not as important to you but its there because mojoportal does support role based security. For example if you create a page and set the permissions so that only admins can view it, the page doesn't even appear in the menu unless you are signed in as an admin and any content on that page will not appear in the search results unless you are an admin doing the searching. Now I'm only talking about view permission in relation to search, a user can have view permission but not edit permission and still can search and view the content.
Is it possible to implement a custom search page that would search across sites? Yes its possible to implement it (this would require coding in c#), though each site hs its own index so you would need to run the search against each sites index and combine the results. But you would only know the user's security context within the current site so filtering results from the other sites based on roles would be a problem. You could ignore the problem and not filter it if you are not concerned about senstive data being seen in the search results. When the user clicks a link in search results to see the content, if the link goes to a different site, his ability to view it will be governed by that site when he gets there. If its on a public page that anyone can view it will work, if not he may be prompted to login or if he is already logged in but doesn't have permission he may get an access denied message. There is a role setting for "All Users" which means the content is public to anyone regardless of role so you could filter for this even across sites since it really doesn't correspond to a role but indicates no role is required to view the content.
Another option is to become a sponsor of mojoportal and hire me to implement support for a configuration that meets your needs more easily. For example it would be possible to build a configuration so that mojoportal could be configured to use a single set of users/roles across sites in an installation and a common search index. In a sense this is changing the definition of a "site" to some extent. Currently sites are meant to be completely indpependent but it would be possible to make it an option to have a related set of sites. At the end of the day the result would not look much different than what you can do now by using a single site and visually partitioning it and assigning roles.
Hope it helps,