The main 4 Ps when dealing with any bureaucracy: Patience, Persistence, Politeness and Paperwork. These are the most important.

The 5th P is Perspective. The person you are talking to is the only person who can help you even if it is only to pass you on to their superior. They listen to complaints all the time. There was someone crabbing at them before you and will be someone next in line. Don't make it personal and take your frustration out on them.