I think , adding votings to a unconfirmed transaction is a solution .
How it works --

1. Someone broadcast a transaction (maybe with tag like dynamic transaction) to p2p network .

2. Each node receiving the transaction see if it’s a valid transaction (say by applying AcceptToMempol/AcceptableInput),

    2a. If successful (Transaction is fully valid ) , give upvote(with some sort of signature )
  
    2b. If failed (Transaction is not good) , do nothing or give downvote

3. Now, Network count the votes,
  
    3a. If upvotes - downvotes >= certain amount of votes (say 100, i.e. upvotes - downvotes >= 100);
          then assume transaction is valid and can be spent, (with proof that it has enough upvotes )
    3b. If downvotes > upvotes ,
          then transaction is not valid and should not be submitted to miners.

4. A transaction having enough upvotes submitted to miners (that in 3a)