Your cat might have a bladder or kidney stone which is causing extreme pain when pooping. Please take your cat to the vet and have that checked out.

I ran into the same thing: Cat pooped in exotic, awkward places, but never the litter box. Never looked like she was in pain -- just being stubborn, I figured. Turned out to be a bladder stone brought on by the ingredients in modern cat food (put in place to help other feline health issues, but which causes stones in a small subset of cats). After the stones were cleared up, all litter box issues disappeared.