I have to agree with everyone on the Nature's Miracle, I've used it for awhile on both cat and dog urine. I even used it in our old rental where I would swear the old tenants just allowed their dogs to use one area of the living room to take care of things instead of going outside. We steamcleaned, scrubbed etc. and still couldn't get it out. Finally we put Natures Miracle in the steamcleaner which got rid of the smell so it definately works on older set in stains.

I agree though that you should call the carpet company back and have them redo the cleaning first if you can.