Yes, this ^^^, I second that the titanium bowties should not be any more durable than steel.
If you do decide to go the cleat wedge route, I think the Lemond "Lewedges" are now marketed under a different name by Bike Fit Systems (http://bikefit.com/products.php
Regarding the rocking, I would have to assume that if it is side to side rocking or "Roll on the X axis" that we are discussing, and it is coming from pedal wear not cleat wear, then wear to the plastic body is probably the source rather than wear to the bowties.
@Cattiy, did you simply try new cleats yet? That would be a good start for the process of elimination/troubleshooting. If the majority of the play remains, then I would guess that you are suffering wear to the left and right plastic/resin portion of the pedal platform.
You may be right that, for long term prevention, a different spindle length might help. My take on this whole issue is that abnormally fast wear (outside of a particularly abrasive operating environment) is probably due to uneven loading, due to some idiosyncrasy of an individual's pedal stroke. I am sure you have all ridden in a paceline and noticed the knees or feet of person in front of you wobbling in or out on each pedal stroke, or noticed a kind of bow-legged or knock-kneed leg posture that distributes the majority of the pedal load to the very edge of the pedals. The high point loading, combine with the constant movement/grinding that tends to come from that sort of instability seems like a perfect mix for high wear.
Before you make any fit adjustments, I would ask myself "am I doing this because I think bad fit is causing accelerated pedal wear, or am I changing my fit to accommodate weak equipment". It can be tough to tell the difference, but it should go without saying that the former is a great idea...the latter not so much.
The new Speedplay "Pave" pedal would probably fix the pedal body wear possibility as it makes the whole area steel. I would like to see them come out with a new Zero pedal body with a steel cross shaped plate rather than a bow tie to achieve the same end with the Zero, but have not heard any plans for that. Replacing cleats 1 time per year is something that I can take, but more often than that, or having to replace the whole pedal body yearly due to wear is simply too much for me to tolerate.
I am just coming up to the 1yr mark on my current set and am watching them closely to see how much play develops.