After much browsing I have bought myself a messenger bag made by a little company here in NZ - "Cactus Climbing"
Interestingly they don't show this bag on their website.
It is made from heavy duty canvas and lined with truck tarp PVC. Has a D-lock sleeve, 2 zippered pockets plus one in the flap. Dimensions WxHxD is 47x43x17 cm (I'll let you work out imperial measurements). It has a cross strap and a cell phone holder is optional.
Price is $NZ153 if you can get in on a run of five. They generally only do a run when they have 5 orders. They will do a one off at $NZ200. Plus I guess delivery.
The way the $NZ is against the $US they will be damn good buying.