How can balances not yet rewarded/earned show up in the payout queue?
When work is given, CPPSRB has precalculated everyone's exact reward for if that work results in a block. So if it does, everyone is paid properly. The payout queue displayed is simply a periodic snapshot of this data which includes the rewards for the block not yet found... which can't be included in a manual payout.
Related, what if the payout queue is completely emptied out by a manual payout, and (due to vagaries of the queue and people not yet hitting their threshold) there are not yet enough users in the queue for payouts to total 25 BTC in the currently-being-mined block? Is the remainder just sent to the cold wallet for future manual payouts? Or will the pool just pay out accounts before they hit their thresholds?
It goes to the cold wallet, yes. The only time the pool pays a balance before it reaches the minimum payout, either default or custom, is due to inactivity. Balances < ~0.001 BTC are never paid out.
1) So manual payouts are just normal transactions pushed to the Bitcoin network?
Yes.
I.e., they often end up in blocks that aren't mined by Eligius? If so, it seems that it would be nice to just have that transaction included in the next Eligius-mined block so that the pool can keep the fees (equivalent to not paying fees). Obviously this could lead to a delay in payments if there is a long round, but I think that most people would understand.
I usually just pay the fees, or send it fee-less and prioritize it on Eligius.
2) How often does Eligius push new block contents to miners? If the exact payout amount is fully paid out and kept current (not just the "as of last block" amount) in every block, this would have to be pretty frequent..... several times a minute? So if a miner successfully finds an "old" block (with "old" version of the coinbase transaction that has "old" balances), I suppose the new balance differentials are just kept in the user's account to be paid out the next time they enter the queue?
Each miner individually gets updates every 55 seconds or when a new network block is found. But work is constantly being generated and given to other miners on offset schedules. The result is up-to-the-second work being out there somewhere at all times.
In reality, the share log is paid based on when the work was issued, not when the block is actually found/submitted. This prevents a few unlikely attack vectors like a user finding a block, holding on to it, then adding a bunch of hash power to the pool before submitting the block thinking those shares will be paid by the current round. In reality, they would be put towards the next round since shares submitted after the block-finding-work was issued isn't paid/rewarded by the block.
(Edited a few times for clarity)