But BEFORE you do that, did you actually TEST the check valve, or just see if it was pulling vacuum through it? If the check valve is bad, when you cut the car off, you immediately lose the vacuum that's normally stored because the booster is open to the engine's intact tract. I would CONFIRM that the check valve is good FIRST if you have not done that 100%.
