Uncanny X-Men (1st series) #392
Unyielding molecular structure makes him virtually invulnerable to
outside forces directed against him and capable of exerting superhuman amounts of force and pressure, but leaves him vulnerable to his need for oxygen and can be disabled by overuse
Paulie Provenzano had only recently returned to Brooklyn, New York, after being discharged from the Marines when he sought out a trio of mobsters who ran the local neighborhood. He revealed to the men that he discovered his mutant abilities while in the service and that he was now of the view that it should be who is running the neighborhood, not them. The mobsters instantly retaliated by shooting him with their guns, but unfortunately for them Paulie's mutant power made him indestructible and the bullets did not harm him. Worse for them, Paulie’s Marine training enabled him to take out the mobsters and afterward he warned them to let everyone know that there was a new Paulie in town.
However, Paulie was immediately thereafter visited by the X-Men's Jean Grey, who was in dire need of a team of X-Men. She asked Paulie to join her in returning to the Xavier Institute and Paulie gladly accepted, if only to see Jean in her costume (just one example of his womanizing personality). Upon arrival at the Xavier Institute, Paulie demonstrated another unfavorable characteristic – his homophobia, which brought him into immediate conflict with another of Jean Grey's Interim X-Men, Northstar. Jean managed to break the two mutants up and, after Paulie was given the standard blue and gold X-Men uniform, he and his new teammates learned the reason Jean had assembled them – to stop Magneto from unleashing all-out war between mutants and humans. [Uncanny X-Men (1st series) #392]
En route to Genosha, Paulie, like the other interim X-Men who were not overly familiar with their powers, received a telepathic crash-course on their abilities, courtesy of Jean Grey. [X-Men (2nd series) #112] Paulie's thoughts were not pleasant when Jean read his mind, and even afterwards he continued to flirt with her, despite knowing that she was married to Cyclops. It wasn't long before Paulie's homophobia made itself known again. When the Blackbird the X-Men were traveling in was torn apart by Magneto, the X-Men found themselves falling to the ground below and Paulie protested when Northstar attempted to grab him as he plummeted to the ground. The issue was rendered moot, however, as all of the X-Men were soon caught in an electromagnetic field courtesy of Magneto. When Magneto confronted the interim X-Men, Paulie, like his teammates, were shocked when Magneto seemingly murdered Dazzler. [Uncanny X-Men (1st series) #393]
Paulie reacted to Dazzler's death by attempting to confront Magneto head-on, despite the warnings of the experienced hero, Northstar. Unfortunately for him, Paulie's bravado simply got him sent into the upper atmosphere, courtesy of Magneto. There, Paulie, despite his near-invulnerability, started to suffocate. However, he was rescued by Northstar, who was able to use his super speed to reach the high altitude and pull Paulie down to a ship off the coast of Genosha. Paulie was rendered unconscious and woke to find Northstar performing mouth-to-mouth on him. Paulie accused Northstar of coming on to him, but Northstar explained that he was simply saving his life, although the Canadian mutant was unsure why. Northstar then flew Paulie back to Genosha and Paulie expressed his gratitude with a quiet thank you.
Magneto was soon defeated and all-out war averted. Paulie returned to the Xavier Institute with the other Interim X-Men but, despite being offered permanent membership with the X-Men, Paulie (and the others) all declined, and apparently returned to their previous lives. [X-Men (2nd series) #113]
Presumably, Paulie returned to Brooklyn, although his exact activities immediately following his departure are unconfirmed. A short time later, Paulie was kidnapped by the Weapon X Program, which was herding up mutants and keeping them in a concentration camp called Neverland. Paulie's powers were deemed worthless by the higher-ups at Neverland and, alongside another short-term member of the X-Men, Maggott, Paulie was led into a chamber and gassed to death. [Weapon X (2nd series) #5]