My hunch is that if you get paid and your client isn't up and running (and up-to-date) when the payment occurs, you get cast into the void of payments that take forever.
Nah, when a payment is broadcast (either through sendmany or by a single client), all that matters is that other nodes relay the payment.
The receiving client doesn't even have to be online; That's why offline wallets work.
The only thing which isn't a constant is priority of the payment.
The less tx fee (or none at all), the lower priority it gets in the list of transactions to be verified by miners.
It's safe to say 'everyone' can afford an optional 0.005 fee to get their payment in a reasonable time. I'd pay it every time on deepbit.