I think it would be better if it was moving faster than a high yield plasma shot, but slower than a photon torpedo. I also think they should be able to see it, and possibly get a warning (audio or otherwise) that it was incoming, but could do something to hide from it.
For example, this probe thing sees bits of radiation or whatever are leaking out of the cloak, so maybe if the cloaked ship stopped, or dropped to a very low speed and allocated power to aux it would lower it's energy signature and send more power to the cloak to the point where the probe thingy would lose it completely.
Personally I have no problem with the way the cloak works now. The only changes I'd make is I'd make it harder for a ship with lots of hull damage to cloak. When fighting a few ships with cloak it's annoying when you hammer the ship, and then an almost dead BoP just cloaks and runs off for a bit. I'd also kill (or darken quite a bit) the lights on the nacelles, and the impulse trails on Fed ships that have masked their energy signature.
If anything I'd weaken science ships' ability to see through the cloak, and make it something any group of X many ships can do when together, regardless of class or tier. So more like a sensor net/triangulation thing, instead of a "science ships have better sensors" thing.