The thing is, you'd buy Scout if it were useful, and you won't buy it if it weren't. Altering its cost won't change that. The biggest problem is that Scout doesn't draw a card if it doesn't pick anything up, so I wouldn't take it even if it came for free a lot of the time.
Exactly. To fix Scout, you don't need to change its cost, you need to change its text. Would making it a cantrip be enough?
Or what about:
+1 Action
Look at the top 4 cards of your deck. Put them back in any order.
+1 Card
That actually fits with the name a little better, and I think might be an okay card, even at $4. But maybe too similar to Cartographer?
The fixed Scout is Vagrant.
And that's a $2 card.
Draw 0-4 Victory cards (with reordering): $4
Draw 1-2 cards, one of which is a bad card: $2
KC-ing a Vagrant leaves you with a 6-9 card hand, 3 of which could potentially be bad.
KC-ing a Scout leaves you with a 3-15 card hand, 12 of which could be bad, but only VP cards, not even Hovel makes the cut.
I like the first option better.
The thing with Scout is that you might think it makes the next turn great, hooray! But with a fairly normal and random distribution of VP cards you might draw 1 or 2 from it and that's just plain awful. This means the net effect of Scout is basically zero: Instead of getting the Estate in your next hand, you get it in this one. And I don't like buying cards that often have a net effect of zero, certainly not for $4 which is a pretty competitive price point. You could get a Silver for less!
Compare it to Pearl Diver, once you find a bad card on the bottom of your deck (or good one that you want to leave), its net effect becomes zero (barring KC, TR, etc.) and that too is a $2 card.
Playing Scout and drawing zero cards (happens often enough I suspect) is basically the same as playing Ruined Village, a $0 card that's dealt out as punishment.
Its opportunity cost just kills it, more so than its actual cost. By the time it could actually be useful, during the end game in which you're flooding with green, you'd rather spend that $5 on a Duchy or that $4 on Estate/Silk Roads/Gardens/Feodum/Great Hall/Tunnel, or of course: Silver.