It's not in 91.409. It's in 91.417, and other chapters, by backwards reference from FAA enforcement actions upheld by the NTSB.
91.417,a,1 requires records for the maintenance, alterations, and, 100 hour, progressive or annual inspections for each aircraft, engine, propeller, rotor, and appliance of an aircraft.
Explain to me how the maintenance records required here can be complete, WITHOUT an annual inspection on the engine you just installed?
This rule applies to owners, not to mechanics directly, but you would be remiss to release an AIRCRAFT back to the owner, with a different engine WITHOUT an annual inspection on that different engine. It would be impossible for him to comply with 91.417.a.1, and since the records require the signature of the person performing the work, this is how the mechanic gets violated for not accomplishing the annual on the installed engine before approval for return to service. Since the mechanic's signature constitutes the approval for return to service, anything he signs for must be in compliance with the applicable regulations, and in the case of an engine swap of an engine that does not have a current annual, he is liable to perform that annual, and make the required logbook entry.
And for the nitpickers, remember that the reg says APPLIANCES too, so yes, you have to be certain that all appliances have a current annual.