I saw the Guinness report a few years back, and while it's clearly only based on statistical data (unless someone believes that they surveyed every human being on planet earth, lol) it doesn't surprise me that Pac Man is so popular.
Many people here may be too young to realize just how big Pac Man was when it debuted in the '80s. In the same way that Super Mario Bros is largely responsible for home gaming becoming mainstream, the arcade of Pac Man is largely responsible for mainstream acceptance of video games in general. It was a bigger phenomenon than Pong, Space Invaders or Donkey Kong, IMO. Since there is anecdotal evidence going around in this thread, allow me to present this:
When I was 5 or 6 years old was when I first saw Pac Man. I had seen arcade games before that, but I never gave more than a passing glance to a person or two (usually kids or teens) playing one. Then in late 1980 or early '81 is when one of the local grocery stores got a Pac Man arcade unit.
As my mom and I got into the checkout line, I noticed about half a dozen people surrounding an arcade machine at the store's exit. I noticed a kid come up to one of the checkers and ask for change to get quarters. As we left I saw kids and teens huddled all around it, but that wasn't all. There were adults who had stopped to see what it was and were curiously checking it out as well - moms with their shopping carts, a man in a business suit... nobody had ever seen anything like it. It reminds me of the stories we hear about the crowds that the first Pong unit drew back in the '70s (and probably Space Invaders in Japan). It was happening all over again. It was the game that got me into gaming; after witnessing the sights and sounds on screen I couldn't stop thinking about it and bugged my mom that night to take me back to the store later when there would be less people so that I could actually try it. I didn't have to pester her much though because she was curious to play it as well.
I know... "cool story bro", but my point is to illustrate that Pac Man was the Wii Sports of its day, no doubt, and it was everywhere in pop culture for much of that entire decade. Even with Mario being present in Donkey Kong/DK jr, Mario Bros, Super Mario Bros and the record breaking SMB3, I would still credit Pac Man as being more recognizable in the mainstream... back then.
Having said all of that, the undeniable fact is that Pac Man, unlike Mario, has simply not had sustained popularity for almost three full generations of people now. In fact, after Ms Pac Man the character's popularity became a bit dormant once the late '80s/early '90s hit until Championship Edition debuted in 2007.
Bottom line, there is no concrete way to prove who the most recognizable video game character is. All we can do is make assumptions based on logic, and in doing that I believe the answer is Mario due to the sheer number of games (including spin-offs, of course) that he has been in, in addition to the fact that his popularity and pop culture recognition has never wavered (and has in fact increased) since his debut.
