FireWA- who did you speak with at the WA DOH ? I'm a NREMT-Paramedic, and am a Licensed Paramedic (LP, just a regular paramedic with a degree) from Texas. My school is in the letter of review phase with the CAAHEP and had been issued the letter before I graduated.
Washington State will not certify me as a paramedic. I've spoke with different people at the office and have mailed in my application several times. Still won't certify me. My school is still in the LOR phase, and has never been denied.
So I'd definitively double check whatever you've been told before committing to a non accredited school so you don't find yourself in my position. Luckily I'm also a police officer so I'm doing that FT and not out of a job.