Thanks for that suggestion. We have now tried video chat initiation with the "Enable AIM Relay" switched off on one side, and then on both sides of the conversation partnership. No joy ... we are still only able to achieve one-directional invitation and session initiation.
Today I was on several phone calls with technical support for upc-cablecom, my ISP, they assured me that they do not block _any_ UDP or TCP port numbers. They agreed, however to send me, at no cost, a new cable modem to rule out any possibility that their premises equipment (specifically a Scientific Atlanta EPC-2203) was causing this problem. Note however that the new cable modem from upc-cablecom will be from a different vendor, UB.
In the interim, while waiting for the cable modem to arrive, I replaced the Apple Airport Extreme base station (that we use as a router/access point) with a new one.
After that component change, we have the same symptoms ... iChat/Messages video chat invitations sent from US to Europe will work, albeit after several tries. But reverse direction fails consistently, with communication error or a false report that the other side declined invitation. We are coordinating actions on both sides using text chat concurrent with video chat invitation attempts.
Those same partners cannot be invited from either our Mac mini or from the MBP. This was working beautifully for the past three years and suddenly we started having issues.
Replacement of the cable modem is next on the agenda... timeline is for new cable modem to arrive in 1 to 2 days.
If degraded equipment is the root cause of this problem, we will know after we have replaced everything possible ... we get there when the new cable modem comes. (all that is left to change is the cable modem)