(1.16.2) What is the most efficient way to /spreadplayers into a different dimension?
Your idea may be the best you can do.
It seems like our friend Fabian Röling has pointed out a bug report about this issue. Because it has been confirmed as a bug, it means that /spreadplayers should not act this way.
Therefore, to answer your original question, the theoretical most effective way to /spreadplayers into a different dimension is one of your original trials:
execute in minecraft:overworld run spreadplayers 0 0 0 45 under 30 false @e[predicate=namespace:in_nether]
But because of the bug, it doesn’t work. And you had to find a workaround.