I have incompatibility troubles too. I have narrowed it down to the way I compressed my material. I am using Final Cut Pro and DVD SP. If this is relevant to you, I have found that when you compress using Quicktime Conversion the bit rate peaks and fluctuates and the cheaper DVD players cannot handle the high bitrates. I have since been told that if you compress using Compressor the bit rate is a lot more stable and doesn't fluctuate as much and the spectrum of machines can handle the bit rate as their defaults are set because they don't peak at levels higher than what you have set.
From what I've learned, when you burn as opposed to replicate, you have an 85% chance that your DVD will play in most machines. Replication is closer to 100%. Since it's unreasonable to replicate every DVD you do (due to price and timing), it seems like this is a chance we all have to take.