Here’s a simple but still imperfect take: switch the blockchain over to self-targeting minfees so that inclusion in the next block can be more easily guaranteed. Then, just trying to send a transaction into each shard at the same time should have a >90% success rate in any given shard, so would require trying ~1.11^N times for a cross-shard transaction affecting N shards.
This is probably most problematic against malicious proposers; to defend against this, we could have the execution be over a 2-block range instead of a 1-block range.