My best advise would be to contact a company that provides this service to the construction industry in your area, let them know you are interested in using their company for future jobs and see what they tell you. They may be very informitive, and giude you in the right direction all in one call. In Florida there many guide lines (such as time limitations upon completion). On larger jobs it's easier to hire a company to handle it for you. Once you know all the rules, it's not to bad to handle the smaller ones inhouse. Here, I believe they can also just post a bond in the amount owed and you've wasted your time and money. it's been awhile since I've dealt with NOC, NTO and releases.
Best of Luck, I hope you get paid.
R