After adding a TXT record with the public DKIM key for a domain hosted at GratisDNS.dk, the zone stopped updating. Querying anything returned the configuration and serial from before the DKIM key was added.

The explanation is actually in the Wiki on GratisDNS itself, but took me some time to find:
Too long TXT records (over 255 chars) cause updates to fail, though it's not really obvious since the GratisDNS webpage will show them just fine.

Take for example a key like

v=DKIM1;p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC75PoYNkZ5MPJSi36gzr/pXTaoYaikVB97IQPGFF0k4TjFl6HjUy3bMVR1cMF6kNfBsSCt2xNIKXKvGZEHhZEXFWOi+9JnkBUMIpiyjU2JRFk25RnTBAr+IXTCJcba6w92ZC5IRTFaauI0o9m7ckehBTNQ8a5G5Za4SleRBcukjwIDAQAB

Since it's over 255 characters long we need to break it up in bits with double quotation marks.

"v=DKIM1;t=s;p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC75PoYNkZ5MPJSi36gzr/pXTao"     "YaikVB97IQPGFF0k4TjFl6HjUy3bMVR1cMF6kNfBsSCt2xNIKXKvGZEHhZEXFWOi" "+9JnkBUMIpiyjU2JRFk25RnTBAr+IXTCJcba6w92ZC5IRTFaauI0o9m7ckehBTNQ" "8a5G5Za4SleRBcukjwIDAQAB"

However to make it a little more tricky, GratisDNS actually adds the first and last quotation mark themselves, so what you actually need to input in the TXT value field is

v=DKIM1;t=s;p=MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQC75PoYNkZ5MPJSi36gzr/pXTao" "YaikVB97IQPGFF0k4TjFl6HjUy3bMVR1cMF6kNfBsSCt2xNIKXKvGZEHhZEXFWOi" "+9JnkBUMIpiyjU2JRFk25RnTBAr+IXTCJcba6w92ZC5IRTFaauI0o9m7ckehBTNQ" "8a5G5Za4SleRBcukjwIDAQAB

Querying the record with dig @ns1.gratisdns.dk <selector>._domainkey.example.com TXT will show spaces between the quotation marks, don't worry they are ignored/stripped out when the DKIM lookup is done.