MPEG4 format madness - iPod and Creative Zen Vision and Sony PSP

In the process of  trying to figure out video podcasting (vodcasting) for  the most popular portable devices (ipods, Creative Zen Vision, and Sony PSP), I've discovered that MPEG4 as it's supported in the real world is a mess of incompatibilities.  In my streamingmedia.com article on interactive MPEG4 authoring a few years ago, I noted that interactivity in the MPEG4 spec was not really implemented by  any major vendor.   Now I see that almosr three years later, even the basic video codec profiles are not  supported in a meaningful way.  

I've been trying to find the codec/format combination that will work on an iPod, a Creative Zen Vision, and a Sony PSP.  All of these purport to support MPEG4.

• iPod handles MPEG4 SP and AVC in an .mp4 container
• Creative Zen Vision handles  MPEG4 SP, but only in an AVI container. Leading tools like Sorenson don't even bother to support this archaic variant.  I might as well use the WM format's better compression and drop MPEG4 from the process. 
• Sony PSP - I've just ordered one for testing, but in advance of its arrival, I've already noticed that the .mp4 AVC files that Google Video makes available for the PSP are different than the .mp4 AVC files they make available for the iPod.  And tests reveal that the PSP-targeted file will not play on an iPod.  

I guess I  thought there'd be more support for common standards in 2006 than there was in 2003.  When I'm done testing, I'll post the recommendations on what codecs/formats will work on most of the popular devices.  Seems that no one has really tried 'em all (and written about it) from the content publisher's perspective - "what's the simplest process for supporting the most users?"