Thanks for the detailed comments. For a) I can see how that is true when using anyone-can-spend outputs (OP_TRUE), but how could the miner change the destination if it worked like I described?
1. User negotiates with n number of nlocktime-relay nodes and receives their fee address
2. User creates n number of tx's, each with a standard fee and an output to the nlocktime-relay's address

(I'm just realizing that I don't know at a low level how transactions fees are added to transactions, the tx fee wiki didn't have much. Are they just anyone-can-spend outputs?)

Using this method the outputs are fully defined and signed in the tx (except for the normal fee), so the miners couldn't modify the output to the nlocktime-relay anymore than they can modify outputs of blocks today (I think).

There are obvious downsides like the negotiation and manually broadcasting the nlocktime'd transaction to each relay, but still possible.

however you are one step ahead of me with (b) and I don't have a great response.
With a theoretical hardfork this nlocktime'd fee being paid could be unlocked a certain number of blocks before the rest of the transaction is unlocked and broadcast. Maybe it could be a somewhat complex system where it costs the nlocktime'd fee slowly becomes available so these nlocktime relays can slowly drain this fee. But if you're sending this to 10,000 nlocktime relays they all leach off a fee... bleh

The better option is to come up with a new nlocktime since we're basically trying to solve usecase #2 from here. Where (with a hardfork and a new lock time construct) we could insert the locked tx's into blocks, but not let them be spendable until the lock expires. Solves a lot of the broadcasting issues, and seems like the more needed usecase for locked txs.