As you suspect, there isn't an easy way to achieve this without an exponential explosion of GPOs. Or by manually assigning groups, which probably isn't an option for you, either.
Try looking at your clients from the perspective of roles instead of "what software is installed?" and/or "where is this machine at?" The physical location of the client, after all, probably doesn't matter from the viewpoint of what updates it receives. For example, typically all the accounting workstations have a set of software installed (or could have a standard set) and all the operations workstations have a set of software installed. This becomes two targeting groups in WSUS and updates are applied based on what software you already know is in each group by role.
It'd be great if a merge were possible, but I can't sort out a simple solution to your problem even using WMI filtering.
This isn't a great answer, but I feel like it's better than the two you have here.