I work frequently with Indian staff. What I have found as an American is that I have to begin each project with some "cultural training".
My Indian partners often over promise and under deliver. From a US perspective, that is worse than failure to deliver. It becomes important to then clarify what will be delivered and when. It is also important for my partners to understand that I WANT them to tell me what they can reasonably do and when. This way, we can set expectations.
Incidentally, the basis for this is that my Indian partners do not understand that they may say "No" or even, "I don't think that I will be able to do this". So when we discuss the problem, part of the process is helping them to understand that I prefer to hear about limits and they are most welcome to talk to me about them.
I have learned this by working with Indians that understand the culture gap and have been willing to talk openly with me about what they perceive as the differences. It is a great help to me.
You are on the right path when you talk about understanding the culture of Saudi Arabia in order to work successfully there.
From a very high level, I can see that you did not have the proper decision makers involved at the beginning. The people who will not sign off for you are an indication of that- they do not wish to lose face.
Okay. Whoever the decision maker is must also sign off. That means that you engage the higher commander on key points. The lesser officers have their place but the guys that can make commitments are the ones who must sign off.
When I start seeing a lot of requirement changes coming to me from lower echelon officers, I simply call a meeting with the decision makers to ratify the change request- and I make sure that I have communicated with my project initiation that I will do so.
A verbal agreement is worth the paper it is printed on- nothing at all.
I think that you are very sincere in trying to develop a "Lessons Learned" document. One tip- when the project ends before implementation, call all of the players (sponsors, stakeholders, team) into a room and discuss what could have gone better. This will help you to identify what you can do more effectively in the future.
Good luck to you!