A colleague has just given me a clue and it turned out to be the correct answer.
When initializing the PrintServer, if you pass in the path of the machine that the printer is on as a parameter and just use GetPrintQueues() without any parameters, then you are talking directly to the networked machine that is the PrintServer, which gets the updated status correctly.
If you initialize the PrintServer without a parameter, and use the flags as I have posted, it is talking to your local machine which is not getting the updated status until it is re-polled (in this case presumably by the "Printers & Scanners" dialog)