Outback Steakhouse is a restaurant chain that began in Tampa, Florida, in 1988. The nickname “Outhouse Steakback” is a ”“spoonerism” (or transposition) of the compunds “outback” and “steakhouse.”
 
“Outhouse Steakback” has been cited in print since at least 1995.
 
     
Wikipedia: Outback Steakhouse
Outback Steakhouse is an American casual dining restaurant chain based in Tampa, Florida with over 1200 locations in 22 countries throughout North and South America, Europe, Asia, and Australia. It was founded in February 1988 in Tampa by Bob Basham, Chris T. Sullivan, Trudy Cooper and Tim Gannon, and is now owned and operated in the United States by OSI Restaurant Partners, and by other franchise and venture agreements internationally.
 
Google Groups: alt.humor.best-of-usenet.d
Newsgroups: rec.humor, alt.humor.best-of-usenet.d
From: .(JavaScript must be enabled to view this email address) (Eric Swanson!)
Date: 1995/04/25
Subject: Re: Request: Spoonerisms (Re: Oxymoron collection)
 
There is a certain chain of restaurants I have difficulty calling anything but “Outhouse Steakback”
-Eric S.
   
1 December 1997, Los Angeles (CA) Times, “Not Bowled Over” by Mike Downey, Sports, pg. C1:
For all I know, they will end up in that Outback Steakhouse Bowl, or that Outhouse Steakback Bowl, or whatever it is.
 
World of Cynicor
Sunday, June 29, 2003
Outhouse Steakback
Happy Birthday, Julian!
 
HighBeam Research
11 September 2006, St. Petersburg (FL) Times, “It’s the Out House, er, um, Outback blimp” by Robert Trigaux:
“I called the Outback Steakhouse Blimp the ‘OutHouse SteakBack’ Blimp one time,” Gannon told the Raleigh paper last month. “They didn’t like that.”