Closing the loop here, this happened because the stacks that these deployments belonged to were deleted, and we filter out deleted stacks when we return the list of org deployments.
If deployments were unpaused, as the deployments dequeued, we would realize that the stack is deleted and just drop the deployments from the queue. However, when the org is paused, we don't go through that check because the deployment is never getting dequeued. In this case, just unpausing deployments caused the "jammed" deployments to clear up because they went through the regular check during dequeue.
I'll open a bug internally to follow up on this, but just wanted to surface here what the issue was in case this comes up for anyone else.