I am surprised that more major pools don't offer similar services.
I would suspect that:
1. It takes a bit of effort to implement
2. In general, people with stuck transactions are like that because they don't want to pay high fees, so aren't likely to part with large sums of cash to push a transaction through.
3. If you had that sort of money to spend on getting a transaction sent, you'd just pay a high fee to start with
So, personally, I don't think it would be much of a money maker at all... sure, you'd get the odd customer here and there... but making ~$300 on an accelerated transaction when you get US$350K+ per block is nothing... I'm not sure the ROI on trying to implement the payment/queueing system and messing with the pools mempool/transaction selection algorithm is really worth it.
I don't think it would be difficult to implement. I believe many pools give priority to their own transactions, and it should not be difficult to add additional transactions to this priority.
The Viabtc accelerator IMO is marketed to users who are not technically savvy. If they cannot figure out how to double spend their transaction, they will never have a way to ever spend their inputs "stuck" in unconfirmed transactions. (this part could be solved by modifying the nLockTime feature to allow for a maximum block number that a transaction will be valid for, as opposed to a minimum block number).
There are usually over 2,000 transactions in each block. Charging $300 to confirm 1,000 transactions in a found block could nearly double pool revenue based on your example of $350k revenue per block, and charging $300 per transaction.