(1)If the iphone 3G running 3.0 is currently lying to Exchange, why can't an iphone 3G running 3.1 lie also? - Because 3.1 apparently purposely "corrected" the lying.
(2)If it is common knowledge that the 3G running 3.0 is lying, what is to stop Exchange from syncing with 3.0? - Nothing,
(3) From reading this discussion it appears that no one believes that Apple can or will correct this issue? - Referring to your first point, it's because 3.1 is actually a correction. Since the 3G doesn't support encryption (see here:
http://support.apple.com/kb/TS2941) I think Apple believes there's nothing to "fix" as 3.1 is essentially a fix.
kinda sad, eh?