I'm also looking at trying for a PhD after taking a rather non-linear route. I've just finished my MSci and am taking a year to build up the finances, take the GRE and go through the application process. (I took my degrees in the UK so it makes it a little more tricksy getting to interviews and testing centres and the like!)
I think the MS is a great idea if you have a chance to do some research--it gives you definitive proof that you've not become rusty with the general material and have had a chance (recently) to go over the basics and are currently involved in the all-too-happenin' physics scene, such as it is....
I'd *definitely* *definitely* get some research in--that's the main thing I've been asked by PhD programs; what have I *done*. The test scores and gpa only get you in the door.
One of the best things I've done for myself is to write up my work and put it online; even if it's just an overview of a project with an abstract and some basic results, it allows you have something immediate that assessors can access. I also include a page with information on areas of interest to me which I'm trying to tailor to the programmes to which I'm applying. It's made life sooo much easier, being able to point people to a URL and I've already received very positive feedback from grad schools.
I'm running on a bit so will stop myself becoming *too* boring; would be more than happy to compare notes, though, if I could be of any help in any way!
All the best,