Firstly, WHENEVER you are concerned about a change in habit, please call the doctor. It never hurts to ensure that your cat has no physiological stuff going on.

Next. I, too, had terrible troubles with my giraffe-legged boycats. They pee standing up. The pee went into the corner seams of the hooded litterpans and ran down the outside. I bought two 18-gallon Rubbermaid bins. Cut a hole in the top of one, left the top off the other one (give the cats a choice between covered pan and open). Put in substrate. These are deep enough to contain the flow. They're also much cheaper than commercial litterpans. They're large enough for some very big cats to turn around comfortably. All win!

Just make certain that there is sufficient substrate to give the pan decent weight. Cats won't use a pan that rocks when they clamber into and out of it.

Freezetag,
Well, I would suggest you took a urine sample to your vet. Our (only) male cat in the house goes through such "periods", and he is going through one of those right now. Our vet really did not have much to say about that except that it was a male thing. I just happened that I came upon some interesting reading in one of my books (The Natural Cat by Anitra Frazier), and she attributes it to an overly alkaline urine, that would make passing urine slightly painful (and he has to "force it out"), and that it would lead to formation of crystals--which actually, with your cat's past history, might be exactly the case. She also suggests to spread some white paper towels around the box to see if the urine is bloody.
What makes the urine turn too alkaline is what I need now to learn and discuss with our (new) vet. Stress and diet are the 2 causes she suggests. Anyway, I 'll go get my book and quote her exact words. I would be very interested in how you solve the problem.

Good luck, Anne-Marie

(p. 386) If the urethra has begun to swell closed, the cat may have to strain to pass urine. While straining he may straighten his hind legs, lifting the genital area up while he is still wetting, and spray over the side of the box, or onto the wall or floor.

If it is a litter box issue, try the Clever Cat litter box. You can find it by searching online. I think I bought mine at Petsmart. I had one cat who hung her little butt over the side of the box to go and was thus always peeing half way in and half way out. This box (with high sides and a top entry) solves that issue as well as cutting down about 95% on tracked litter. I was so happy to find it; it is a great solution.

I had a kitty who began standing to pee when he got older- I think it was because it was difficult for him to squat down. While you're at the vet's office, maybe have him checked out for arthritis as well.