Sorry no. The users would have to be the attackers (assuming the users' cumulative hashrate far exceeds any attacker and remember I am targeting instant microtransactions so users' cumulative hashrate will be very astronomical with say 100,000 tx/sec). They decide the set of providers simply by choosing where they send their transactions.
The attackers can be both users and providers (you must have considered this?). A user with a majority PoW can also set up a majority of provider nodes, such that he can use his majority control to censor transactions with a greater than 50% chance of success, assuming the minority moves away from the attackers provider node randomly. If you require users to query ALL provider nodes for transactions, this becomes a DOS attack.