We recently released a hotfix for an issue related to missing shadow copies.
The KB associated with the same is:
http://support.microsoft.com/default.aspx?scid=kb;en-us;910330

(910330) - Described a problem where stored shadow copies are overwritten
even if there is sufficient storage space allocated for shadow copies in
Microsoft System Center Data Protection Manager 2006. You must install a
hotfix to resolve this problem.

We would recommend installing this hotfix on all DPM servers in production.

- Balaji Hariharan (Thanks to Karan)