This is a manual promotion executed for the first time.

For 25+ minutes after clicking the manual approval button the promotion status page was showing it as "In progress (log)", but the log link (promotion/Release%20to%20Stage/lastSuccessful) returned 404.

No running build could be seen when navigating to promotion/process/Release to Stage/, it just showed a completed build #25 from 2 weeks ago.
When I tried to start another one it would show #27 in the queue (skipping #26)

Our promotion is a thin wrapper that triggers another job. I can see in that downstream job's history that it has been triggered by the promotion job around the time I clicked manual approval and has been running for 35 minutes.

Around the time the said downstream job has finished the promotion status page started to show the promotion as "Successfully promoted (log) " and a successful build #26 appeared in promotion/process/Release to Stage/ history.

It seems the root cause of the inconsistencies are long running promotions (or ones triggering long running downstream jobs) – once all the jobs finish it seems the plugin gets back to a consistent state.