I don't know about the specific tense of your phrase “They'd very well not done it at all”; rather, I think it all depends upon the author's voice, style, formality and syntax.
Your phrase sounds more "British" English, and thus, more formal; whereas, the sentence "They may as well not have done it." sounds more American English. (This is just to my ear, of course.) If I were to have written the latter (a subjunctive phrase itself), I probably would have phrased it "They may as well have not done it." This way, the stress on 'not' emphasizes the doing of the thing they should have avoided.
The use of the contraction, though, is interesting because it reads better than if written as "They would very well not done it at all." Without the contraction, it seems to call out for a 'have' after the 'would'.
Frankly, I like your construction and have copied it down in my sentence book for later use.