Summary
Bumfuck, Egypt is first documented in army slang from 1972, and BFE is from at least 1988. Bumfuck, [Egypt] appears to be the original, followed by variations Bumblefuck (1989), Bubblefuck (1993) and Buttfuck (1999).
Sometimes these variations appear standing alone, sometimes in Egypt, or Africa (also found in BFA), or another country, (rural) state or place, and sometimes prefixed by East or West. More recently, both BFN and Butt Fucking Nowhere are reported from 2002.
As Bumfuck, Egypt appears to be originally military slang, given the number of abbreviations they used I can easily believe it was also jocularly and euphemistically shortened to BFA before 1988.
Partridge
The Concise New Partridge Dictionary of Slang and Uncoventional English (2003):
BFE noun any remote location. An abbreviation of BUMFUCK, EGYPT US 1989
Bumblefuck noun any remote, small town US 1989
Bumfuck, Egypt noun a mythical town that is the epitome of remoteness. With variants US 1972
It also gives BFN and Butt Fucking Nowhere, both from 2002.
OUP
These 1989 and 1972 first citations are given with others in The F-Word (2009, Oxford University Press):
BFE noun [Bumfuck (or Bumbfuck), Egypt]
Military & Students. a very remote place; the middle of nowhere.
1989 P. Munro U.C.L.A. Slang 20: Troy...lives out in B.F.E....Bum Fuck, Egypt.
Bumfuck noun
Military & Students. a very remote place. --used with a placename, esp. in Bumfuck, Egypt. Also Bumfuckistan. Jocular. See also BFE, BUMBLEFUCK.
1972 Sgt. E-6, U.S. Army: They probably sent those records out to Bumfuck, Egypt.
It also gives Bumblefuck as a 1989 alteration of Bumfuck; Bubblefuck as a 1993 alteration of Bumblefuck; and Buttfuck, usually used with a placename, from 1999.
Usenet
I found an earlier example for the initials BFE in Usenet, on 11th September 1988 in alt.cyberpunk:
$600 is about what we paid for my first computer -- a C64, 1541 and printer; when I was a upper-lower class kid living in the backwoods of
BFE, Leesville, Louisiana. (Ft. Polk sux too. :-). We weren't on
welfare, but we weren't rich either. I think we saved about 9-12months
for the computer. (Grandparents bought me a monitor a month later. What
a rescue. :-). That computer made the difference between me being
a dual major CompSci/Journalism student in Houston instead of being
like my cousins: 2-4 kids, HS diploma at best, slow paying job, no future,
and living in BFE, Louisiana.