I was planning to use the IPTables U32 module to look at the "original packet" which is included in the ICMP packets destined to Skype-related connection attempts but this might not cut it because there are other ICMP messages involved, not just the "port unreachable" I saw at first.
Instead, now I plan to use the "recent" module.
(Note: try running "iptables -m recent -h" to list options not mentioned in the manual. Apparently it's a good thing to do with any IPTables module)
The "recent" module is designed with "keep the bad guys out" situation in mind (by adding attacker's source address to a tempoary list) but with the "secret" --rdest option, which allows me to add destination addresses of outgoing packets, it might be possible to add the IP of any host with which Skype have just attempted to converse to a temporary cache which will allow this host to send back errors and which will automatically expire in a preset time.