The machines used by these autocentres only do a vacuum check, and a vacuum is -1 Bar. But most leaks occur at dry o-rings in the pipework, usually somewhere in the piping between compressor and evaporator, where the pressure is as high as +15 Bar i.e. the vacuum test is not a conclusive test. The reason why the o-rings dry out is because there is oil throughout the piping but the system has not been run for a long time so the seals dry out. Your car is 2004, not sure how long you've had it or how long it's been since the system was running, but on a car that's 12 years old, the compressor and condenser and o-rings will only be ok if the system has been run and regularly serviced continually for the last 12 years.
So what happens is that the piping passes the vacuum test, they put the gas in, then when the compressor starts up and cold air blows out of the vents, you drive away satisfied, and a couple of days later there is no cold air because the gas has leaked out at an o-ring under pressure.
The other thing that can happen as well, is that they test and refill as above, but there is no cold air, either because the compressor does not run, or because the condenser is perished.
Best thing to do is to use the links in #3 to check the compressor clutch and the temperature sensors. If the compressor clutch is working, then the system should blow cold air when they refill it. Halfords Autocentre will also put in UV dye, so if/when the gas leaks out, someone with a UV light can find the leak.