I have not looked at Payflow Link but I agree with both of you - the thing to do is to write a service contract implementation, and it will be very different from the Payflow Pro module.
If they follow the usual model of taking your information via https and returning the answer back via a URL you specify, then your service contract implementation will have to split the Authorize functionality into two pieces - send off the request in the Authorize procedure and write a new Tcl script which gets the response and stores it in the database. There won't be any way of returning a status directly from Authorize, unfortunately...
The existing contract could be modified to have Authorize always store the result in the database, and to never expect immediate responses, but then we lose backward compatability with sites that are using the service contract as it is now.
This is really a procedural issue as much as anything else - is it better to make a major change to an existing service contract, or to write a second service contract which is similar but different? This issue will come up again, so we should decide now how to handle it.
Personally, although changing the existing contract is preferable to me in most respects I think we are stuck with writing a new one, because of the backward compatability issue. But that's just my opinion.