But you couldn't gain a Duchy on the second play, because there are no cards in play!
There could be actions instead of treasures. So, something crazy:
2x Inn, Watchtower, Menagerie, Laboratory, Mandarin, Silver in play. In hand: 2x Counterfeit, 2x HOP
Play Counterfeit
--Play Counterfeit #2
--Play HOP: Gain Mandarin. Silver, both Counterfeits, and the HOP return to the top of the deck.
--Play (virtual) HOP: Gain Inn, shuffle deck.
--Game cannot find HOP for Counterfeit #2 to trash.
--Play (virtual) Counterfeit #2
--Play HOP #2: Gain Mandarin. HOP returns to top of deck.
--Play (virtual) HOP #2: Gain Duchy. Game cannot find HOP that would trash itself.
--Game cannot find HOP for Counterfeit #2 to trash.
--Game cannot find Counterfeit #2 for Counterfeit #1 to trash.
Buy Province. Actions are discarded.
It's a bit ridiculous, but yeah, I think that can really be the only ruling...