Sounds like a weak coil that can't fire through the resistance of the wire. You said you could feel a spark, well a good coil should really give your hand a quite severe jolt! Coil is such a common problem, it's no waste of money to get a new one, just for reliability if it's age is unknown. Otherwise I'd say coil wire is bad unless you tried other plug wires on the coil also.
96 GC Limited V8 245,000 miles Scrapped
04 GC Limited 4.0 264,000 miles
96 GC 4.0 175,000