Does it miss shuffles? Yeah it does. But when it does it gives you very high odds of hitting $5 regardless and in the early game - who cares then?
The problem is that it makes the thing you buy skip the shuffle too. And then it topdecks up to 4 cards, making it a fairly long shuffle. By the time you get through that it's no longer the early game.
How long of a shuffle can it actually be? Let's take the worse case scenario, you draw down to 3 cards on deck and then shuffle to inspect the fourth
Okay. You have 8 cards that are currently in your hand. In the early game you are pretty good odds that 1 in 4 cards will be a green unless you have shelters or a lot of gains. With 9 cards missing the shuffle, you have have
one to maybe
two hands before the next shuffle (anything more requires 9 total gains which is pretty late or you are building an engine anyways). Is this bad? Yes, you see whatever you just bought a turn later ... but we know a few things about what you just bought:
1. It is not a power $2, $3, $4, or $5 - otherwise you would have bought it before Patrol.
2. It is not a Gm - you have copper in play.
3. If it is a Kc, you have low action density.
4. If it is a gold, you want to buy expensive things ... which a de-greened hand does almost as well.
5. If it is a terminal, you might want to grab a village in any event if you want to get a big turn (e.g. Patrol -> Artisan)
The more turns we are talking - where a bad shuffle could mean cards missing the shuffle more, the more likely we are to have cards (like Patrol), that shorten shuffles in the short deck. Likewise, as your deck gets larger the odds of Patrol triggering a bad shuffle fall (for a single Patrol). On the first shuffle you have a 5/12 chance of missing a shuffle (T4 play). On the other hand you have 7/12 chance of making a shuffle shorter (T3 or T5 play). On the next shuffle you will have 14 cards in the simplest setups - and in only 5 positions does it shorten the shuffle. Now things get complicated if you are trashing cards, gaining engine components, or getting multiple cards ... but those are all areas where you are going for an engine or combo and Patrol is pretty nice for making both of those more reliable.
Patrol can make things miss shuffles, but it also makes shuffles happen sooner and more importantly makes it much easier to line things up (e.g. village/draw/Forge). In the early game missed shuffles will be short. In the mid game, theoretically they could get up to a few hands, but most likely we are talking engine and a more reliable engine vastly outweighs one gain being delayed for a shuffle. In the late game it can be harsh, but in the late game, swiping off the green is just so nice.
Frankly, I find the boards here a little odd about "missing shuffles". Yes it is not a good thing of its own right. But the damage of missing the shuffle is directly weighted against how often you shuffle. Scavenger makes a lot of things "miss shuffles", but is an extremely powerful $4 opener on all kinds of boards. Your power card (e.g. Upgrade) hits at the start of every shuffle and who cares if your silver misses a shuffle? Patrol is a just a less extreme version of that, particularly as you can deck track and just decide not to play a Patrol if it is in really problematic territory.