The phrase comes from a story by humorist Will Stanton that appeared in the May 1971 issue of Reader's Digest. The narrator claims that he is subject to "a kind of slip-of-the-ear," leading to his mishearing things. This is the first example he gives:
I was standing next to a woman at one party recently, not paying much attention to what she was saying, when suddenly she came out with the statement that there was no mayonnaise in Ireland.
The narrator delivers what he considers an appropriately witty response. The woman then approaches the man's wife, concerned.
"I'm afraid he's had one too many." she said; "I was quoting a line of poetry—you know, that bit about 'No man is an island.' Well, your husband gave me a blank look and said there is no ketchup in Australia."
Being practically the Platonic ideal of mondegreens, "no mayonnaise in Ireland" was referenced on many blogs. In early 2012, Stanton's daughter Linda Stanton French commented on a couple of such blog posts, providing source information. This in turn led to the story's being available online. Here is a timeline followed by a link to the story.
On February 6, Stanton French commented on a 2011 blog post by Kelly:
"There's no mayonnaise in Ireland" is a phrase my father, Will Stanton, made up for a story he wrote that was published in the May 1971 Reader's Digest.
A few days later, on February 20, she belatedly replied to a 2006 post from a blogger named Jim:
The story quoted in the first two paragraphs of your link is from my father, Will Stanton’s, short story, “There’s No Mayonnaise in Ireland”, that appeared in the Reader’s Digest in May 1971.
Several commenters on Jim's post greeted Stanton French with huzzahs, shared their memories of the story, and bemoaned their inability to find it anywhere.
Two days later, on February 22, Stanton French set up a Facebook page for Will Stanton.
The entire text of "There's No Mayonnaise in Ireland" is linked off that page.