I think saying that something unethical and clearly criminal in nature shouldn't be illegal, because it's hard to detect and prosecute, is a bit like putting a cart before the horse. You don't respond by making it legal: you keep it illegal and prosecute it vigourously, but you also look at how the incentives work, and fix those.
There are approaches to fighting corruption which work: Singapore is a model case of clean government, in a part of the world absolutely rotten with corruption. The trouble here is that paying politicians and public servants properly would be vulnerable to attack by populist political movements, who are ignorant of the way the real world works -- some politicians have as much responsibility, and far more accountability than C-suite executives in the private sector, but get paid nowhere near as much.