I know that
dpkg keeps md5sums of configuration files for each package installed, so it can tell whether they are changed or not when upgrading.
Does it keep md5sums for regular (non-configuration) files as well?
Yes, look at the contents of
/var/lib/dpkg/info/*.md5sums. Strictly speaking this isn't handled by
dpkg; these checksums are generated at build-time (typically by
dh_md5sums) and included in the binary packages.
You can check that the installed files still match their MD5 checksums using the