Whenever I think about rolling up content across Site Collections, I think about leveraging (if possible)
1) Managed Metadata Services (taxonomy and Shared Content types)
2) Search (leverage search scope etc)
3) Some kind of web part to surface the data on the pages.
And efficiency being one of your concerns, Search is your best bet! Nothing can beat its performance!
I have come across a good solution (Extending the Content Query Web Part to Aggregate Data Across Site Collections and External Sources) which might give you some directions: http://www.msteched.com/2009/NorthAmerica/OFC405
Search has its limitations though (the accuracy of the results depends on when the last index operation was run). If this bothers you, you may perhaps end up iterating the lists of your site collections manually as suggested here: http://social.msdn.microsoft.com/Forums/en-US/sharepointdevelopment/thread/d271da25-57f4-4f59-a34d-fd06bc4c8ce6
The lightning web part as suggested in another answer could be a good fit for you. I would suggest to evaluate it (like how it does it internally, permissions, additional configuration, efficiency, caching, control over display etc).