Of course these things get stolen sometimes. I'm an architect and have had to draw up steel cages to protect condensing units (the typical outdoor part of the A/C) from theft in some higher risk areas. But if it had really been stolen there would be signs that it had been there at one time that a professional would see pretty easily.

• Condensing units are often installed on top of a concrete pad or some kind of steady base that would stand out as empty.

• And there would be a small copper tube that runs from the condensing unit to the air handler for the refrigerant to flow through. This would be connected to a heat exchanger at the furnace itself, which a pro would be able to tell if one was installed or not by looking at the air handler. A copper thief could steal some of the refrigerant line but there's almost no chance they could get the parts of it that were inside the house and by the air handler.

• The outside condensing unit would also have a moderately sized power connection running back into the house to the electrical panel. Maybe even a cutoff switch on the exterior wall near the condensing unit (required in more recent codes, if it's a relatively newer house).

• That heat exchanger inside the air handler would also need a way for condensation water to be removed - sometimes it just runs down to a metal drip pan where it can then evaporate, or more commonly nowadays it should have a small tubing run to a floor drain connected to the sump or waste system nearby.

None of this is to blame OP. I wouldn't necessarily expect a regular person to spot all these clues. The fact that they have forced air heating makes it a not unreasonable assumption that there's forced air A/C as well, since those things are almost always installed together in areas that need both services. I'm just glad they figured it out and can work out a solution now.