Yes, “at work” is an appropriate response
The primary definition of “at work” as given by every dictionary I could find is merely that one is doing their job—it has absolutely no primary association with being in a particular place, nor does describing both individuals as being “at work” imply they are working for the same company.
doing a job:
- Bob’s at work on that software.
(Cambridge English Dictionary definition for “at work”)
to be working:
- The laborers were at work in the fields.
(Cambridge English Dictionary definition for “be at work”)
If someone is at work they are doing their job or are busy doing a particular activity.
The salvage teams are already hard at work trying to deal with the spilled oil.
(Collins English Dictionary definition of “at work”)
- Engaged in a job or other activity, as in The contractor is hard at work on the new building, or The little boy was fascinated to see the washing machine at work. [Early 1600s]
(Dictionary.com definition of “at work”)
“At work” means I am currently doing my job,
(English Language & Usage Stack Exchange, highest-rated and accepted answer to “‘In work’ vs. ‘at work’”)
engaged in work.
- in action.
“researchers were convinced that one infectious agent was at work”
(Oxford Languages definition offered on Google.com for “‘at work’ meaning”)
- engaged in working : busy especially : engaged in one's regular occupation
(Merriam-Webster definition for “work,” specifically the section on “at work”)
Some of these sources offer secondary meanings of “at work” as having to do with the place of business. Many also do not. (Many more note other uses of the phrase that aren’t relevant in context here.)
So in answer to the primary question here,
When people ask him how he and his wife met, can he say, “We met at work”? Even when they work at different companies and usually don't work together?
The answer is emphatically Yes, he can answer in that manner.
Answering with “through work” is also acceptable, and might avoid some ambiguity, as some listeners might understand “at work” as implying at that particular office. Most, however, will not, as that is not the primary definition of the phrase.
If the question was asked “Where did you meet?” (which would ordinarily be the same question as “How did you meet?”), there might be somewhat more reason to use “through work,” as the combination of a question asking “where” with the preposition “at” may be more likely to cause listeners to understand the answer as referring to a place rather than a circumstance.