The TXT entry outgoing-alex._domainkey.leidinger.net which worked for a long time suddenly stopped being delivered by named (thanks to Henri Hennebert for the HEADS-UP). Every other query I try works so far, it is really just this one entry (resolve timeout). I notified the responsible person, investigation is ongoing.
This means that any verification of my outgoing mail will not work, as the data necessary to verify the signatur is not available. 🙁