The link provided by Pinkfreud has Robert St. John’s recipie at the end. Mr. St. John is known as an excellent chef 'round these parts, and I’m embarrassed to say that I didn’t think to search for one of his recipies. :o
Just for you, cowgirl, I will do some more searching and perhaps we will find the best come-back sauce recipie. 
When making a sauce using mayonnaise, why not use eggs and olive oil?
O.o
I see. Ok.
Apparently, come-back sauce is Remoulade sauce with a Mississippi twist. Perhaps my OP would have been less confusing if I’d said “Remoulade Sauce”.
Here’s some results from digging around on the Web:
Come-back Sauce
http://www.recipezaar.com/173437
For fried chicken fingers
http://www.recipezaar.com/27515
A Remoulade sauce
http://www.recipezaar.com/57296
From the Hollywood Casino in Tunica, Mississippi:
1 1/2 c mayonnaise 1/4 c ketchup
1 1/4 c chopped celery 1 1/2 T worchestershire
1 1/4 c chopped green onions
1/2 c choped parsley 1/4 salad mustard
1/4 c white vinegar 2/3 c horseradish, processed
1/8 c paprika 1/4 c fresh garlic
1/2 T hot pepper sauce 3/4 T salt
1 T lemon juice
1/4 c Creole Mustard
Another Southern Living recipie:
1 c Mayonnaise 1 T chopped onion
1 T chopped parsley 1 T chopped gherkins
1 T capers 1 T prepared horseradish
1 T lemon juice or white vinegar
2 T dijon mustard 1/4 t salt
1/8 t hot sauce 1/4 c vegetable oil
1/2 t Worchestershire 1/2 t anchovy paste
Dratted formatting.
BTW the T = Tablespoon; the t = teaspoon.
Upon preview: Excellent suggestion, carnivorous plant.
Oh, Lord-a-Mercy, Comeback Sauce!!!
It really is a Mississippi Thang. Not to be had up here in NC. I developed a taste for it from John Currence’s great restaurants in Oxford, mentioned in the Clarion Ledger article linked above. I loved his Fried Dill Pickles dipped in it, and love fried okra dipped in it as well. As said, no one serves it here, so I make my own. Just had some day before yesterday, with fried okra.
That basic recipe from Southern Living, augmented,** by yers truly
COME BACK SAUCE
1 cup mayonnaise
1/2 cup olive oil I leave this out, the mayo has enough oil, really
1/3 cup chili sauce PLUS a good tablespoon of Horseradish. You could just do a half cup or so of ketchup without the chili sauce then.
1/4 cup ketchup
2 tablespoons water
4 teaspoons Worcestershire sauce to kick that up, add a generous dash of Piccapeppa sauce. It’ll make it darker in color, but adds a sweet taste
4 teaspoons prepared mustard, *** or a teaspoon of Coleman’s Dry mustard, for intensity. Don’t just use yellow mustard, it has no flavor. Spicy, or Creole, is better.
2 teaspoons coarsely ground pepper
1/8 teaspoon paprika Get a good brand, dark in color. If it has no whang of smell, it has no taste either
1/4 teaspoon hot sauce **Real hot sauce, not Texas Pete, the ubiquitous dull and nasty stuff here in NC. Louisiana hot sauce, or Tabasco
I also add, depending on what’s at hand:
*Celery seed, crushed
*Pickle relish
*Capers, chopped, an aquired taste
*A dash of Tamari
*Dash of Bourbon, adds an odd complex note. Moonshine good for that too, but harder to come by
*Tried Wasabi, and it lights up your sinuses. Prolly too intense for the kids,but found it tasty
*Dash of balsamic vinegar
*dash of Pomegranite syrup, YUM!!!
Yeah, I love that comeback sauce, amazing that it hasn’t spread further. Hmmm, to 1000 island dressing, it’s 100,000,000 island dressing, and really wakes up the tastebuds.
Damn, I’m missin’ Mississippi.
OK, blame PMS for this hijack: no ‘ie’ on ‘recipe’. It’s not ‘reciPIE’. Then again, this is a thread about ‘come back’…
See, PIE is a code word in Southern speak for good eatin’ A reciPIE means y’all should pay attention to things like comeback sauce and fried okra. You could reference this as well with a search to the SD meme of "Pie’, or “Comeback with Pie”, but, you’ll find it’s not a sauce at all, then; it’s more in the happy retort category. Cheers!
Dear G-d, I made some tempura with the first fresh okra of Spring this week. Some of the tempura sauce of Soy, sugar, wine and garlic. It was great. Mrs. Plant of Long Island would have none of it, bless her little heart.
Okra is the Devil’s vegetable.
<blech>
Not even in jambalaya.
See, this is the problem. Okrys need to be harvested young, and tender. A lot of the crap okra is nasty and old-beyond harvest. It’s rare that anyone gets excellent okra.Problem is, it cannot be mechanically harvested, just doesnt lend itself to that. Really great veggies, but way misunderstood.
When you cook yer okry right, comeback with PIE!
It ain’t jambalaya without okra.
As my Sainted Mother would say, G-d bless her, “Ya’ll just don’t know what’s good.”
Huh? I’ve had jambalaya down in New Orleans, and I don’t think I’ve ever seen it with okra. My friend, born & bred down in NO, doesn’t make her jambalaya with okra, either. Gumbo, yes. Jambalaya, I won’t say “no,” (I’m sure somebody must make okra jambalaya), but I haven’t encountered it, and my standard recipe sources don’t have okra in the jambalaya.
A. Okra is a food of the gods.
B. Born and reared up in Texas, summers with cousins in Alabama, never heard of Come Back Sauce.
I read it the same way. I interpreted it as an unusual phrasing for fanservice. I was sad to see it was just a cooking thread. >_>
Mercy! Y’all DO need to come back to Mississippi. 
Thanks for the recipie.
Carnivorousplant, make her some of that pop-corn fried okra fron the first little sprouts. It’ll make a puppy pull a train. 
Then I must stand corrected, unless there are more Yankees living in Louisiana than I thought…
My mother used to say he same thing to me when I was a kid. The hell of it is, she was right! Fortunately I developed a taste for those things and was able to tell her so before she died.
And carnivorousplant, it’s actually gumbo that has to have okra in it as an essential ingredient. In fact, the word “gumbo” comes from the Bantu word kigombo, meaning okra.
True, however there are okra-less gumbos made with filé powder (which comes from sassafras). The general rule is if you make gumbo, it’s one or the other, never both. Then there is another offshoot of okra-less gumbo that is thickened with roux. Plenty of respected NO chefs, including Paul Prudhomme, make such gumbos, in addition to the traditional ones. Personally, even though I’m not from the area and I really can’t lay any sort of claim to the cuisine there, gumbo to me means either okra or file powder (preferably okra).
No, dear, that’s “cum-back sauce.” Neither rude nor offensive, just a fact of life. And yeah, one of the few recipes that you make in a jar.
I loved salmon croquettes when I was a kid!
See the second comment in post #30.