It was more than 10 years ago admittedly. However, I don't pay bribes as a matter of principle. Had they not accepted my application even though it was complete and asked for funds without receipt, I would have gone straight to their superior, and up and up. I've done that with other government offices and never paid anything. You have to talk in a polite and friendly tone, use the right vocabulary etc.
It helps if you do negotiations for a living, so the accountant might not have been the right person to discuss with them on your behalf, I don't know that. Sorry to hear that you gave up, but maybe you want to reconsider. They can change the regulations for the LTR at any time, and on the other hand, the automatic work permit is of course very nice.