The last round of hiring we had guy's from the military who did not have an ATPL. They either had the requesite time and did the ATPL ride along with their initial type on an Air NZ bird, or they did not have the time and did the ride down the road. So it really didn't matter. You'll need to be able to get an ATPL at some point, but it shouldn't take much more then 16-18 months to get the 1000 hours FO. Perhaps that is what Margy is talking about.
As far as your military time I don't know. I flew with a chap the other night who was in the US Airforce for a spell on exchange. I assume he had the same deal. As they want to see your military record at the interview stage, along with your log book, it might be not that big a problem.
So can I assume that you have applied? If not do it today (remember the six months). And get that PR visa. And check your PM's.