There are ${12\choose 2} = 66$ combinations, and $3^3 = 27 < 66 < 81 = 3^4$, so the best possible solution would be $4$ weighings. So all we need to do is find a plan that will always succeed in at most 4 weighings.
Step 1
Weigh (1,2,11,12) vs (5,6,7,8). This yields 24 cases where the scale tips left, 24 cases where it tips right, and 18 cases where the scale is even.
Tips Left
In this case, both 11 and 12 must be correct. Specifically, either 1 or 2 is swapped with one of (3-10) or 3 or 4 is swapped with (5-8).
Step 2 Weigh (1,12) vs (2,11). This yields 8 cases for each result.
If it tipped left, we know 1 is one of the swapped eggs. If it tipped right, we know 2 is one of the swapped eggs. In either case, we need to determine which of (3-10) is the other. To determine which:
Step 3: weigh (3,5,10) vs (4,6,8).
Tip left: one of 4,6,8 is the egg. Weigh (4,11) vs (6,9).
Tip right: one of 3,5,10 is the egg. Weigh (3,11) vs (5,9).
- Balance: one of 7,9 is the egg. Weigh (7,12) vs (9,10).
If Step 2 balanced, we know one of the swapped eggs is 3 or 4, and the other is one of (5,6,7,8).
Step 3: Weigh (4,5,6,7) vs (1,2,8,11).
- Tip left: one of the pairs (3,8) or (4,8). Weigh (3,12) vs (4,11).
- Tip right: one of the pairs (3,5), (3,6), (3,7). Weigh (5,12) vs (6,11).
- Balance: one of the pairs (4,5), (4,6), (4,7). Weigh (5,12) vs (6,11).
Tips Right
If the first weighing tipped right, then the procedure is much as above, swapping left vs right, and reversing the order of the numbers. A bit of rearrangement is needed to make the scales balance for step 3.
Balance
If the first weighing balanced, then there are 18 possibilities, with both swapped eggs on the left, both on the right, or both unweighed.
*Step 2: * Weigh (2,4,6) vs (5,7)
Tips Left. The swapped pair must be one of: (2,11), (2,12), (4,9), (4,10), (6,7) or (6,8). Weigh (1,4) vs (2,3) to determine which is the lightest swapped egg. Then weigh (1,X) vs (X+1) to determine which is the heavier swapped egg. (Eg. (1,9) vs (10). Tips left indicates 10 is light, tips right indicates 9 is light).
Tips Right. The swapped pair must be one of: (1,2), (3,4), (5,6), (5,8) or (7,8). Weigh (5,8) vs (1,12). Tip left: the pair is (5,6). Tip right: (1,2) or (7,8). Balance: (3,4) or (5,8). One more weighing is needed, at most.
Balances. The swapped pair must be one of: (1,11), (1,12), (11,12), (3,9), (3,10), (9,10), or (5,7). Weigh (1,4) vs (2,3).
Tips left: The lighter swapped egg is 1. Weigh (2,12) vs (3,11) to find the other.
Tips right: The lighter swapped egg is 3. Weigh (1,9) vs (10) to find the other.
Balances: The pair is one of (11,12), (9,10), or (5,7). Weigh (5,6) vs (9,2) to determine which of the three.
In all cases, it is possible to determine which pair is the swapped pair in at most 4 weighings. Since that is the minimum theoretically possible, that must be the answer.