Yep, instances are asynchronous and can handle long running processes. As for cg-bin circa 1996, I appreciate your long memory! But nothing was RESTful back then. ;-)
In the end, doesn't the implementation of the executable partly determine whether it is really RESTful?
Certainly long-lived URI's. As for resources, I suppose conceptually there is. However you are correct that the given executable would determine a level for resources. So I guess the answer is YES. Support for RESTul is RESTful. Or not, depending upon your executable.