"International Man of Mystery" was the soubriquet of a great stage and TV magician David Berglas, who used it in all of his publicity material. His is still alive, but his heyday was the 1960s and 1970s. It amused me at the time because it seemed to say a lot, but at the same time said nothing. It was a brilliant tease. I used it in the programme biography notes to describe a performer in a comedy show that I produced in the early 80s. There was another member of the cast in that show, a comedian called Neil Mullarkey, who went on to form a double act with a young, upcoming comedian called Mike Myers. Neil also liked and remembered the term, and passed it on to Mike. That's how Austin Powers got the title. I have recently been in touch with David Berglas (indirectly through his son) and explained how Mike Myers ended up with it. For him, it was a big mystery solved, and I've been told that he forgives me, which came as some relief to me after decades of slightly nagging guilt.

I was expecting to see a question about Austin Powers. This doesn't directly answer your question, but it does say what this phrase means to me.

It means a spy, like James Bond. “international man of mystery” = man from secret services.