This sounds worse than Eastern Europe. My wife once had interactions with Polish authorities and the first official told her immediately what amount of bribe money will be necessary to get it done quickly, contrary to everybody involved sitting it out as long as possible. When she asked why the bribe is so high, the government employee explained to her whom of his colleagues he has to pay himself to get it done quickly.

I respect your refusal to pay bribes, but I believe you would have already received your approval if you were willing to pay a bribe. Not sure much those delays cost you in regards of your time invested and lost opportunities.

I'd go to the first person you talked to, ask how much needs to be gifted to him personally so he/she can take care of this. Then pay half of it at the beginning and the second half once you have received your approvals.