ACLs are taken into account by Alfresco's search functionality, so that won't be an issue.
Assuming the departments never share content (which would strongly imply a single repository), I'd say it's mostly a question of operational cost - having a single uber-Alfresco instance will be less costly to maintain (backup, tune, scale, etc.) than having a plethora of smaller instances. That said, there are some relatively rare cases where different departments could collide in their usage of a single instance; for example if one department requires complex customisations to the Alfresco logic or UI.
Perhaps start out with a single instance as a "straw man" and see how far you can go with it? You might find that that model will work well for a majority of the departments, and the small number of special cases each deserve their own dedicated instances.
Cheers,
Peter