This problem is not fully solvable without dummy records:
Let's call the state when the current version is version 3 "state 3", and the state when the current version is version 4 "state 4". No matter how you sign these states - as long as the attacker is telling you "state 3 is the current one" (showing you the entire database as it was during state 3), you can't know if this is true or if state 4 exists in the meantime.
Thus, you will have to periodically sign "no change" updates. You won't be able to avoid the signing overhead, but you don't have to store all of these. You make a separate "lastupdate" table:
Signer | Last | Timestamp | Signature
TA | 4 | 2013-1... | (TA;4;2013-1...)_TA
TB | 3 | 2013-1... | (TB;3;2013-1...)_TB
meaning "Signer TA confirms that as of 2013-1..., the last version sent by me was 4". If the storage provider cannot show you a current confirmation from all signers that they didn't issue a newer version, you have to assume that he is hiding something (or something broke - either way, the data is not up to date). Any new signed statement replaces the older ones from that signer, because they are irrelevant now.
Now, if you don't have just one versioned "thing", but a large number of them, you don't necessarily have to have one such dummy log per "thing". For example, you could calculate a hash (or hash tree) over all the most current lines by your signer (e.g. "Thing A, Version 3. Thing B, Version 7. Thing C, Version 2.") and then just put the hash or the root of the hash tree in the lastupdate table.
If you really want to avoid additional signatures, and some things get updated all the time, you could include the hash and timestamp in the signatures of the version records you sign - the most current signed record would then be sufficient proof for freshness, and if it were too old, you could still use the "lastupdate" table. This is not worth the complexity, IMHO.