On my les paul,

When I check the intonation on the low E and A string, the 12th fret note is flat. Oddly though the saddle piece is adjusted all the way possible toward the headstock (making the string shorter).

Still though, the note is flat. What is going on?
You know the trick to take out and flip the saddle? It will give you a tiny bit more room for adjustment if the saddle stops before it reaches the "wall" on the tune-o-matic.