Stupid question, can't this trivially be solved by having a movable constructor / builder type that then gets turned into a non-movable type when built?

Sure, thats one reason why IntoFuture and Future exist. Imo, in hindsight this is also main mistake in aysnc Rust: The whole async system should be build around IntoFuture rather than Future (async fn should return impl IntoFuture).

That way you could pass around IntoFutures without being affected by auto traits leaking. Only when you actually call .await() or .poll() would the immovable Future materialize.

You're right that this is an important issue. I wrote a post explaining this in some detail, so at the very least we avoid having the same problem with generator functions:

https://blog.yoshuawuyts.com/gen-auto-trait-problem