Let me demonstrate the difference with some examples.
First a normal ssh connection to a new host. Without VerifyHostKeyDNS it doesn't matter if your SSHFP records are up-to-date, since they won't be checked.
$ ssh login@example.com
The authenticity of host 'example.com (127.0.0.1)' can't be established.
RSA key fingerprint is 01:23:45:67:89:ab:cd:ef:01:23:45:67:89:ab:cd:ef.
Are you sure you want to continue connecting (yes/no)?
With "VerifyHostKeyDNS yes" and up-to-date SSHFP records, it looks like this instead. Note the extra line of output.
$ ssh -o "VerifyHostKeyDNS yes" login@example.com
The authenticity of host 'example.com (127.0.0.1)' can't be established.
RSA key fingerprint is 01:23:45:67:89:ab:cd:ef:01:23:45:67:89:ab:cd:ef.
Matching host key fingerprint found in DNS.
Are you sure you want to continue connecting (yes/no)?
And this is what you get, if the SSHFP record ain't up-to-date:
$ ssh -o "VerifyHostKeyDNS yes" login@example.com
[Cut long line of @'s. Too many 'junk' characters for /.]
@ WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED! @
[Cut long line of @'s]
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
01:23:45:67:89:ab:cd:ef:01:23:45:67:89:ab:cd:ef.
Please contact your system administrator.
Update the SSHFP RR in DNS with the new host key to get rid of this message.
The authenticity of host 'example.com (127.0.0.1)' can't be established.
RSA key fingerprint is 01:23:45:67:89:ab:cd:ef:01:23:45:67:89:ab:cd:ef.
No matching host key fingerprint found in DNS.
Are you sure you want to continue connecting (yes/no)?
Compare that with the first case where you had absolutely no idea if the fingerprint was correct or not.
I'm not saying, you should just trust all SSHFP records, if you're paranoid. But even if you ain't paranoid, the warning about the mismatching SSHFP record should be enough to make you stop and think instead of just saying yes.