I got some specs from Optilabs recently, and cannot fault their service. In my case, Vision Express (Staines) were also a bit funny about giving me the PD, but I found an easy way to do it was to take a photo of myself holding a ruler in front of my eyes while I stared into the distance. Load the photo into the computer, zoom right in and then draw vertical lines from the centres of my pupils down to the ruler - job done, to sub-millimeter accuracy.
In my case, I didn't get on with the Optilabs frames - the ones I chose looked bad on me, and also I found the lenses were a bit too close to my face (eyelashes were brushing the lens all the time), so I emailed Optilabs and returned them under their 7-day satisfaction clause, and they refunded my credit card no questions asked. Can't fault that. For anyone else using Optilabs, I would recommend calling them first and getting some sample frames sent out, so that you can make sure the look & fit are good before you place an order.
Next, I popped into Vision Express in Brighton on a day out, and tried on all of their Oakley frames until I found a pair that fit me and looked good. When the guy there was measuring my PD, he was happy to share it with me, and it matched my DIY measurement perfectly. I love the Oakleys, and for the kind of lens I got (gold iridium coated, slightly tinted, with Transitions light-reactive darkening) they were about the same price as the Optilabs equivalent (£275).
Cheers,
Darren