Yeah, I think we're talking about user profiles that were intentionally removed though ... I only skimmed the original post before now, so I agree with you in terms of 'a regular page' and would not recommend using Gone for those, but if the pages were removed for a reason, will not ever exist and they were (most likely only) linked from within the site, Gone would seem to be the right answer.
In reading the OPs situation with a bit more detail, Gone may or may not be correct, personally, unless they want those pages indexed at some time in the future, I would probably use it ... Even if someone adds content to the pages, what value do they add to the results? I think they would be for 'on-site-use-only' if they do ever exist and Google probably doesn't need to index those, so I'd personally be inclined to lean toward the use of Gone in this situation.
Good point on 'regular pages' and again I would not recommend using it for pages with significant in-bound links, I'd definitely find a way to redirect those and 'capture' the link weight if I could.