The /var/lib/dpkg/availabe/var/lib/dpkg/available can be recreated from the apt data. The easiest way I found to do this us using dselectdselect and choosing update. I expect this will only work if you have apt chosen as your update method. Seems like dselectdselect does a: /bin/bash /usr/lib/dpkg/methods/apt/update /var/lib/dpkg apt apt Note
/bin/bash /usr/lib/dpkg/methods/apt/update /var/lib/dpkg apt apt Note though things may have changed since Debian sarge.
There are tricks to recreate /var/lib/dpkg/status/var/lib/dpkg/status based on the fact that every package is required to add a directory in the /usr/share/doc/usr/share/doc directory. See post at http://linuxmafia.com/faq/Debian/package-database-rebuild.html. There is a script presented that uses a filtered listing of /usr/share/doc to create a list of packages that were installed, then reinstalls them all.