I would suggest multiple approaches at the same time.
#1 - You want to avoid having a business that is 100% dependent on Google traffic, so it is very smart to develop backlinks that will drive real traffic. Reach out to relevant forums and blogs that have your target market and can directly drive sales to you. If the Google penalty gets worse or never improves, you won't care because you will be getting so much traffic from non-Google sources. Google tends to notice websites that are getting real traffic and reward them.
#2 - Keep trying with the reinclusion. It can be frustrating and I do have doubts about how carefully Google reviews them but if it was my site I would be relentless. I would make sure to be very obvious about the large amount of effort to clear any potential sign of manipulation. I would want Google to be impressed and feel that I am not trying to trick them.
#3 - I would also audit my website. Find the low quality pages and fix or delete them. If you had some black hat pages just kill them. Create entire new content sections. A great website will attract backlinks and high usage which will help to replace the missing link juice that you lost when you removed or disavowed those poisonous links.