You shouldn't be able to place a straight-edge along the frets and have them line up, that would indicate no relief.
Get thee to a tech or luthier and get a full set-up and fret dress if necessary. As has been mentioned, nut, saddle, frets, new strings, relief, and anything else which affects the geometry of the guitar.
Fwiw, I've encountered quite a number of older instruments which apparently were designed for heavier strings than what folks commonly use these days, and some tweaking of the saddle has usually fixed the intonation.
The worst fixes might include re-situating the saddle or re-setting the neck, but those don't sound like your problems. At any rate, without seeing your guitar, a thorough diagnosis is impossible.