Depending on the type of service, it might add validation data and then
timestamp, or timestamp as a way of asserting validity, or just add
validation data, in which case the client could then call another service
to get a time-stamp.
Or just report the results of a validation event as of a particular date and time under its digital signature, if the relying party will accept this statement as a certification from a trusted third party, even without a timestamp.
Is this possibility covered somewhere else in the requirements document?