This is being blown out of all proportion in my opinion.
You do the quote, they give you a purchase order, you do the work and then you bill them.
If they have sent you a works/purchase order, then legally they have agreed to the work and your terms and have agreed to pay you once the job has been done to their satisfaction.
Normally on the first job they will send you a form which outlines their terms and you will have to sign it to say you agree to them (watch out, it can often have payment terms in there of up to 120 days, if you don't agree with this, amend it and then sign and return). You will normally have to send H&S etc for the first job too.
You will be lucky to get a building company to pay anything at all up front, but you should be able to part bill them (make an 'application' for part payment) as and when sections of work are completed.
Hope this helps
Andy