Well, the simple answer is to simply create a "webservice call" metaobject which contains all the info needed for the call (I guess preferable raw XML data, one attribute for the header and one for the body) and then simply create a scheduled event which runs every x seconds and tries to fire off all the webservice calls.

When a call succeeds, delete the object. If it fails, leave it so that you can retry it with the next iteration.