Are you sure your wideband is operating properly? 18:1 at cruise is approaching the point where the A/F mixture should be having trouble igniting. If you actually had those A/F ratios, you should be failing NOx, not HC/CO.
Besides the high HC's, if your NOx is still pretty low, it's a sure sign that:
A) You are running rich despite the wideband reading, especially if CO is also on the higher side.
B) There's something wrong with your wideband.
First, see if you can lean it out more - if you can raise the cruise A/F ratio higher than 18:1, your wideband is definitely giving a faulty reading. Pull the wideband out and inspect it for fouling. Try recalibrating it (consult the instructions for your wideband) - you're technically supposed to recalibrate them every 6 months to a year or so. See if the reading changes, and then retune the A/F ratios.
Alternately, there might be something wrong with the equipment at the shop. I've noticed here in Cali that the really cheap shops don't clean or take care of their emissions equipment. I failed at one shop, then went to another that was a bit cleaner for the retest (without really changing anything - I couldn't really find anything wrong with the car) and looked like the equipment was better maintained (it was also a bit more expensive) and I passed just fine. Pay special attention to the probe they stick in your exhaust - if it looks damaged or fouled with carbon, it can have problems getting a correct reading.
It's not impossible to pass with no Cat, but it is difficult. Change your oil, and then give the car an "Italian tune-up" before you bring it to the shop. Aka, go take it for a hard drive (this is more important for getting the Cat hot, but it can still help)
If you can determine that the wideband is reading properly, you might be running too lean, or have fouled or damaged spark plugs - listen to the engine to see if it's missing, as that will definitely raise the unburned hydrocarbons through the roof. Also, recheck your base timing - if it's retarded too far, that can also raise HC.