I've played a few more times with it, it's all right, and the Province gain is occasionally very useful and neat.
I believe it's still clearly underpowered, though, when you compare it to other tfb cards at the same price point.
Fact is, if Curses aren't around, you'll have trouble finding Victory cards to feed into this, since Estates are pretty much the only thing it can trash efficiently, and are thus long gone.
I'm not sure about what to do about it. Lowering the price to 2 could work, and shouldn't break anything, and it would make it more competitive against other trashers just in virtue of its opening-friendly price. And then I can be content having it as a cute little trasher that is situationally powerful.
Another option could be putting a bigger carrot at the end of the tfb stick. I was thinking "gain two differently named Victory cards", so that you can still feed good victory cards into it and get out some value. But here, I'm afraid that it might create degenerate strategies, mini Rebuild-style. Also, the interaction with Colonies and some alt-vp migt be toxic.
I'm not yet sure what way to go, and I'd love to hear your thoughts and/or suggestions about possibilities beside those I wrote above.