Gherald, is your definition of synergy subjective?
Festival+Library do synergize, because together they offset negatives/deficiencies of each other in a way that makes them behave in a way that's greater than the sum of what you can normally use them for.
How is Festival+Library different from Festival plus other draw-to-x? Are they all instances of synergy?
How is Festival+Library different from Library plus other disappearing village giving +$ and +buy (I can think of Villa)? Are they all instances of synergy?
Village/Smithy, Village/Patrol and Fortress/Catacombs are all very similar and slightly different. What's the difference between one set of differences and the other?
[Village/Smithy] do useful additive things that harmonize well, but are not "synergetic" in a way that distinguishes them from what they already bring to the table in other kingdoms.
So is your definition of synergy something like "In expectation it holds that Strength(X + Y in the context of 8 random cards) > Strength(X in the context of 9 random cards) + Strength(Y in the context of 9 random cards))"? I think this captures your notion of "what you can normally use [X and Y] for".
('8/9 random cards' is shorthand for 'in a kingdom chosen uniformly at random among those which have X/Y/both', and maybe the right hand side should be combined with 'average' rather than 'plus'.)
Something I think is true of this definitions: if we assume terminal draw is stronger (in expectation) on boards with villages, then smaller the probability of having a village on a random board, the more likely it is that each particular <terminal draw, that village> pair is an example of synergy, simply because "Strength(X in the context of 9 random cards)" gives a lower weight to the strength of <X, that village>.
So, with my proposed rigor-ification of your (Gherald's) definition, whether X+Y exhibits synergy is a function not only of X and Y—and maybe the other cards in the kingdom—but also the set of cards that are not in the kingdom but are in some other kingdoms. I think that's a bad feature for a definition of synergy to have; I think it should merely be about the interaction of X and Y.
My proposed formula might—I haven't really thought this through—be a good definition of what I would call "relative (magnitude of) synergy".
Village+Smithy [...] [both] do useful additive things
Do you think Village does something useful in the 1-card kingdom {Village}? How about {Village, Baker}? How about {Village, Baker, Harbinger, Warehouse, Minion, Highway, Ratcatcher, Rebuild, Forum, Chariot Race}, or any other kingdom with Village and 9 non-terminals? Do you think, like I think most people think, that Village only does something useful in combination with terminals?
Consider the following variant: flip three coins; if they're all heads, include Smithy in the kingdom, otherwise don't. Then add Village and random non-terminals to the kingdom. Play a normal game of Dominion in this kingdom. Do you think Village and Smithy have synergy in this game? (If it's true only for some probabilities of including Smithy but not others, why does the probability matter?)