I know for requested items I can get around this type of issue by deleting their workflow context and setting their approval field so that the workflow gets kicked off again like the record was just approved and ready to run. For requests, it could be the same deal where you delete the workflow context perhaps but not sure how that would work for a request.
If you want to keep your workflow, you could set a field on workflows that allows multiple runs and then set the condition to be approval is requested on a request and it's active--kick off the workflow. Or you could have your script kick it off. The issue is that running a new workflow will generate new approval records. You would not re-use old ones.
The issue is that normally when a request is rejected, the workflow completes and the request is inactive. You'd be reopening it, resetting the stage, kicking off a new workflow or restarting the old one. It can be messy.
Run multiple option that is not normally visible on workflows can be added by going to your workflow version and adding the field. Please note that this will allow many versions of a workflow to run on one record so in this case, more than one workflow to run on that request record.
