Noah found the following:
$ perl bm.pl
Benchmark: 100000 iterations of [%Y-%m-%dT%H:%M:%S%z]
POSIXDate(avg): 1.396331e-05 sec/iteration
DateFormatDate(avg): 9.172891e-05 sec/iteration
POSIX::strftime is faster, and issues less (unneccessary) warnings.
Thus, SOAP::WSDL's date, dateTime and time classes should use POSIX::strftime instead of Date::Format