If you are paying them to do something they're supposed to do but refuse to do in a timely manner, that may be legal. It's called a facilitating payment or grease payment, and is an exception to the Foreign Corrupt Practices Act.
Ask a real lawyer, obviously.