Transaction fees will remain the same if they are a percentage of the amount transferred.

However the fees would need to be sufficient to justify the expense of running a node, therefore the code would have to be very fast.

Yes, transactions will be written to the blockchain. Bigger transactions will probably be split into more fragments; therefore more blockchain bloat for bigger payments. But the blockchain will still be prunable, and transaction size is much smaller than zerocoin. So XC is still a promising design.

I meant thousands of wallets other than the recipient's wallet.

Yes I know about the dust threshold. It's important to prevent blockchain bloat. I imagine XC will have a dust threshold.