Second, you could use two separate hot wallets, one for medium and one for fast withdrawals. You'd need to manage these carefully, perhaps by splitting your total available funds between them. Then, you can configure your system to draw from the appropriate wallet for either medium or fast transactions. It might not be the best idea though..
You have spoken well Hatchy and I support using two separate hot wallets for this, permit me to add little more logics to your response, This is the deal, create a logic to filter withdrawals with respect to the highest fee (fast category), those of lower fees (Medium) and finally for the last (slow). Use one of the hot wallets for only fast category and the other second one to mix other transactions in the event there are more in the fast category than you can batch at once (for example, of you batch 100 transactions at once, you include all remaining from the fast category which maybe 60, then select 30 from the medium and finally 10 from the slow category or you can even leave out the slow category, only to add some of them after a given time frame), this would ensure that the transactions that are in the fast category are given adequate priority, while those in other categories receives minimal attention with respect to their position on the respective withdrawal queue).
because technically medium user requested before the fast user and we’ve got no UTXOs. If I don't follow this rule, those who are on medium would stay pending until all fast withdrawals are processed, and if there are thousands of withdrawals, it could even take days for a medium withdrawal to be processed.
Fast users are always top priority, but you can create a logic to address medium users transaction being considered stuck. Make a count of these transactions in each category filtered as I mentioned earlier and add them to the second hot wallet in percentages. Example 60% for the fast transactions, 35% of the medium and 5% of the slow transactions and keep it up like that. Additionally, you can create a withdrawal tracker to inform users who requested for withdrawals of their position in the queue. This would help soothe their nerves and give them hope that their transactions are in the process of being sent to the mempool and they can monitor the progress by themselves instead of bugging your support network.