Hopefully this will help anyone else who stumbles upon this thread.. Several hours later, and extrapolating from another thread regarding mass changes across an entire server, I have now performed this on only a handful of domains and can confirm that it works.
For a subscribers primary domain, the Plesk switch works just fine, turn it off, then back on again, DNS entries created and DomainKeys work.
For any other domains, you can do the same thing at the command line (turn it off which removes the entries - if they're still there, then back on again which regenerates the DomainKeys DNS entries correctly for that domain):
/usr/local/psa/bin/domain_pref -u your-domain-name.com -sign_outgoing_mail false
Give it a few seconds, refresh the DNS zones view in Plesk to confirm if you like..
/usr/local/psa/bin/domain_pref -u your-domain-name.com -sign_outgoing_mail true
Again, refresh in Plesk and there's your DNS entries back!
The -sign_outgoing_mail switch tells Plesk to use DomainKeys signing for that domain, /usr/local/psa/bin/domain_pref -h will give you more information about the scripts full capabilities.
(CentOS 6.5 x64, Plesk 11.5.30 Update #41)