Hi @Lauren,
We had similar issues (and still do to an extent), for us the main solutions were pretty much what you've suggested.
As an alternative you could try creating another general Service that's visible to both of your departments. When a ticket is identified as being with the wrong department, create a 'Linked' ticket using the new service. The process for that one could be to mimic the Summary, Description etc. of the original call and then each department should be able to assign it to the other without needing to be granted full visibility over all tickets in each other's queue.
This is only a thought though, we haven't tried it ourselves.