> IOW, maybe you should have called `package-refresh-contents`

I've tried that, but it doesn't work.

> Org has a messed up package versioning scheme, so maybe that
> got in the way (tho IIUC it should not be an issue here).

Could be. Though even if so, shouldn't adding (org . "gnu") to
`package-pinned-packages` demand that org be used from the gnu
repo even if it's built-in?

From a quick step through with the debugger it appears
that (package-install 'org) quits at `package-installed-p` in
`package-compute-transaction` without looking at the version,
which probably means I'm missing something.