Forcing a package re-installation
Apt thinks that the packages are installed and upgraded. Manual verification and testing of libssl suggests otherwise, so the package database is inconsistent with the installed files (maybe files were previously upgraded previously without package manager involvement). For whatever reason this happened, the package is not being correctly upgraded or reinstalled. This assumes that it has been established that the system is reporting fixed versions, but is still showing as vulnerable.
First, attempt to forcibly reinstall the affected packages:
apt-get install --reinstall libssl1.0.0
If that fails, try forcing the complete removal of the package without involving any of Apt's dependency management and sanity checks:
dpkg --force-all --remove libssl1.0.0
At this point, the system is effectively 'broken' because libssl is missing and many packages are still installed that depend on it (this is what Apt tries so hard to prevent, and the reason we are going behind Apt's back), so reinstall libssl1.0.0, re-downloading the latest package from the repository:
apt-get clean && apt-get install libssl1.0.0
Alternatively, if you have downloaded the known good deb package, you can use dpkg to install and force overwrite of any existing files:
dpkg --force-overwrite -i libssl1.0.0_1.0.1-4ubuntu5.12_amd64.deb
Re-test and check (debsums, sha1sum) the installed files against known good configuration.