Couple thoughts come to mind:
1) Since a fulfillment house is handling the envelope closing, can you use a standard design envelope without the opening near the flap? (I think you went with the double flap version to save the effort of peeling off the self-adhesive protection strip.)
2) In the USA, a normal business envelope is identified as a #10 size, and is available in tyvek as well as paper. A tyvek envelope should be handled by the fulfillment house machinery just like a paper envelope in terms of printing directly on it, etc. but it is much stronger than a paper envelope.
http://www.amazon.com/Quality-Park-Lightweight-Anti-Microbial-R2010/dp/B004NYB7QA is one example. I doubt very many rulers will punch through tyvek, although given enough mishandling by the various post offices involved, I suppose it's possible that some small percentage will fail, but those can be handled on a replacement basis.
Hence, a standard #10 envelope (whatever the Australian equivalent is) but tyvek not paper would seem to address both your problems and should be well within the fulfillment house's machinery capabilities. Tyvek is a bit more expensive than paper but it avoids the need for a bag and associated labor which I suspect more than offsets the increased envelope price.
If the fulfillment house would do it at the same price and if the envelope price is similar, I would probably go with an end loaded tyvek envelope.