The best solution is probably NOT Excel.
What you are describing is really a large relational database. While you may be able to brute-force Excel to try to behave like a relational database, that is NOT what it was designed for, so it typically does not handle it to efficiently.
You would be better off trying a database solution, such as Microsoft Access or SQL. If those are not possibilities, then I would recommend investigating trying to use Power Pivot, which allows you to do database-like functions in Excel. We have a separate forum for help on the Power Tools (appropriately called "Power Tools"). There are some Stickys at the top of that forum with some information on those tools.