In case anyone else runs into this / so I can Google it…
W3C has their own time format, and the specs for Sitemaps, at least, require its use. “1997-07-16T19:20:30+01:00” is an example. Yes, that’s a literal “T”.
For people with a standard strftime(), “%FT%T%:z” appears to be what they expect.
Edit: Google, at least, is exacting. %z gives something like “-0400” while the protocol calls for “-04:00”. The date manpage specifies that %:z will use the colon, but PHP’s strftime(), at least, does not support this. Bugger.