I had stains like that all over the ceiling of my 340 when I got it. They weren't really black, just darker than the ceiling color. Big circles and splotches in the main cabin and quarter berth. It was like someone with some weird stuff in their beehive hairdo kept bumping it against the ceiling. Like the movie you're probably thinking of now.
But nothing would remove the stains, until one day cleaning something else, I sprayed a ceiling stain with the Fantastik I was using, then got distracted and didn't wipe it down until a few minutes later, it came right off! Got all the stains off just spraying, waiting a few minutes, then wiping down. And they haven't come back.