Twilio evangelist here.
What you have looks really close. Lets look at passing back the Recording SID in scenarios where the user presses one since thats relatively easy to do by using the action URL your setting on the Gather verb to hold some state for you:
action = baseUrl + "/api/Recording/Delete?recordingSid=" + recording.Sid;
Now when the user presses one, Twilio will make a request to the Action URL which includes the recordingSid parameter.
Once you've deleted the Recording, you can just redirect back to your Messages endpoint to continue to listen to more recordings. In order to keep track of which recordings you've listened to already, you might need to pass some additional parameters in the action URL that can you can pass through your delete workflow and back into the listen workflow.
Hope that helps.