As a former DoD Linux admin (one of the first for that organization), the best way I've found to keep everything in sync is to build updates yourself (essentially, you're doing the vendors work for them). I know of the guidelines you speak of and the regular advisories and it was quite a task to implement something reasonable. In the end though, the only way I could both satisfy both the security concerns and maintain the rpm database integrity was to build updated versions of the vulnerable software myself and install them.
`rpmbuild` is definitely your friend. Build a template spec, then as you need to update versions, you just modify a few details and away you go.
I worked primarily with Red Hat at the time (though I am working with SuSE now) and had the same problems you've described. They (the vendors) typically do not update quickly enough and if you ask them for direct support, you usually get the run around. The "minimum" version issue is particular painful, as it will show up, even if the vendor backports (I'm assuming you're catching these when running the "unix" scan util).
So long as the updated rpm "provides" everything the old version did, you should have no dependency issues. Good luck.