Wynot,
I've always believed that the "once an 8(a) always an 8(a)" is an urban myth, but haven't ever found anything that specifically deals with that idea.
One GAO case that comes close is Ahntech, B-401092. In that case, the maintenance of a range was removed from the incumbent small business (Ahntech) and awarded to an 8(a). One of Ahntech's complaints was that "the Air Force previously expressed a clear intent to reserve the requirement for small businesses by virtue of its obtaining these services from a small business for the last 8 years." The GAO wrote "the SBA does not support AHNTECH's argument that 13 C.F.R. sect. 124.504(a), by its language, applies merely because a requirement has been historically set aside for small businesses." GAO didn't spend much time dismissing that basis for the protest.
I know Ahntech doesn't specifically answer your question, but I think the case can be fairly interpreted to mean that the so long as the circumstances are appropriate, requirements can be removed from a particular program.
I think its also interesting that in your quote from the SBA, it only says that 13 CFR 124.503(f) requires the SBA notified of an intent but doesn't say anything about SBA approval.