OK, long post but it really doesn't say half of what it could have. This is a process that has helped me a little along the way.
Why do I see accidentals used when I see players do fills in a tune in the key of C?
I'll assume you know the difference between Melodic and Harmonic Minor keys and Major keys, and why they sound different.
Therefore you are referring to what you perceive as out-of-key accidentals.
Lead sheets do not contain any information other than the melody line. You need the three stave music to learn modulation technique.
The three staves in sheet music are, "Melody, Accompaniment, Bass" the accompaniment will modulate during the song, the melody line (generally) won't. A single melody line cannot teach you the different tones and sounds that fit a song. Sheet music can help you. It doesn't have to be hard format, many people now use electronic devices.
It will be impossible to find even a classical composer who hasn't used accidentals. Music is much freer than the strict parameters we sometimes like to apply.
Suppose those pianists you refer to as playing in the key of C were actually playing in A minor? Well, Harmonic or Melodic there will be "black notes" and they are in key, they already know that.
If you look at the sheet music for The Beatles "Yesterday", (Three Stave, not the lead sheet) it has accidentals but they are still "in key".
It opens with an F chord but the first note of the melody is a G! Arguably that opening melody line chord after the first two bars is a Fsus2. It can't be an F9 because there is no E flat 7th note to "9th" it from.
The very next bar opens with a B natural in an E minor 7 chord. Everybody knows the B is flattened in F Major and D minor,* which is the key Yesterday is written in.
Look at that dull, plodding trad intro, but the first two bars of the melody are different to the key. To strict theory rules this is anarchy!
As a lesson I would recommend getting the sheet music for this song and studying it carefully.
Notice how good that Melodic Minor line sounds, plenty of accidentals.
Playing three stave music will give you much more experience to apply to lead sheets.
If it sounds good it's okay.. but what are the chordal rules that govern this?
Perhaps those people playing in C are playing in the so-called Blues scale of C, this has E,G and B flats as well as G natural.
There are so many versions of scales and any of the twelve notes can be found somewhere in them. So every note on the keyboard fits at least one version of every scale set. So that every note can be played in one scale or other of a particular root.
Imagine giving a piano to Oscar Peterson or Glenn Gould and saying, "Sorry, it has only got the white notes of the C major scale."
I once bought a book called "Scales and Modes" published by Flame Tree Publishing**, I'm sure other books are available, however, I will list the scales it shows for each note on the keyboard, I will only list C.
C Major Pentatonic,
C Lydian Augmented,
C Natural Minor (Which I believe is really the Aeolian Mode but has been stolen by "experts". Personal view and a long story.)
C Harmonic Minor,
C Melodic Minor,
C Minor Pentatonic,
C Half Diminished,
C Phrygian Major/Spanish Gypsy,
C Lydian Dominant,
C Diminished Wholetone/Super Locrian/Altered, (What... I mean... C'Mon!!" Your just making these up as you go along!)
C Neapolitan, (Bring your own ice-cream)
C Leading Wholetone,
C Lydian Augmented Dominant,
C Lydian Dominant with a Flattened 6th (Back to making 'em up...)
C Major Locrian/Arabian.
C Semi-Locrian with a flattened 4th
C Super Locrian with a Double Flattened 3rd(!!)
C Bebop Dominant
C Bebop Major
C Bebop Dorian
C Byzantine/Arabic/Double Harmonic Major. (Really pushed the boat out with that little beauty!
That is a total of 31 Scales of C major and all 11 other notes on the keyboard, 29 of the scales have accidentals, many having both sharps and flats and some have naturals.
C Diminished, C Chromatic and C Semi-Locrian with a flattened 4th, have sharps, flats and naturals!
Now, those pianists playing black notes in C, I wonder which scale, or mode they were in at the time.
Not only, unsurprisingly, all notes are contained in different keys, but all 12 notes are even contained in ONE specific key!
I think you may find it a big help by reading sheet music, not lead sheets, you will learn a lot more about the structure of music that you will gradually be able to apply to lead sheets, making them even more useful to you.
Sheet music improves the reading of lead sheets. Lead sheets do not improve the reading of music.
* Just to explain, a B natural occurs in the following F scales, - Lydian, Lydian Augmented, Lydian Dominant, Diminished, Chromatic, Wholetone, Leading Wholetone, Lydian Augmented Dominant, Lydian Dominant with a Flattened 6th, Semi-Locrian with a flattened 4th, Super-Locrian with a Double Flattened 3rd.
** Neither I nor any of my family are connected in any way to Flame Tree Publishing.