You can use 'C-x <up>' in the compile prompt to complete on past commands.

This is indeed a lot closer to what I want, however it still lacks a lot of
things compared to my solution. 

Unless there is some package/mode I don't know about, It's a lot less
dynamic, for instance I can't keep typing to reduce possible items. 

There were many proposals how to implement `eager-update' to update
*Completions* as you type.  We just need to put together all parts.

I'm probably out of my depth here, as I'm not very familiar with *Completions*.
Is there a good reason to stick to it when `completing-read` works well and as far as I can tell
does a very similar/the same job?

I have a patch almost ready based on Philip's feedback that I will be sharing today or tomorrow.
If, however, the consensus is that it's not a good fit and that `C-x <up>` and *Completions* is good enough,
that's fine by me.