Okay, here's a major clue for working out the correct chords to a melody.

First of all, the assumption, "With a bit of trial and error I discovered that the chord that sounded right would always have the relevant melody note in it somewhere .  .  ." is not guaranteed to be correct. It depends a great deal on the placement of the note in the measure (on the beat or off?) and the duration of the note (long, or just a passing tone?). If you try to put a chord to all the notes in a melody, you will a) be very busy and/or b) go quickly nutso!

A simple, straightforward approach is to sing the melody while playing, presumably, a guitar or other chordal instrument, starting with the tonic chord (C in the key of C) and sit right there until the melody and the accompanying instrument "clank!" Sound bad together, or at least just don't sound right. Then, try one of the other two chords. One of them should sound okay. Then keep going on that chord until you come to the next "clank." And proceed thus through the song until you have the chords worked out.

Once you do that, if you want to, and you think the song can take it, you might experiment with substituting an occasional relative minor chord to see how it sounds. Trial and error.

Even classically trained musicians (which I am) have to rely on the ear to tell them what works. I can look at a melody line in written music and get a pretty good idea of what chords to use—but—I can't really be sure until I try singing the song and experimenting with the chords, as I have described above.

Here's something to note:   Assume two experienced musicians may work out the same song. Most of their chords will be the same. But not necessarily all.

Example: Do you know the song "I Ride an Old Paint?"

At the end of each verse, most song books give the chords on the last line of each verse as (say it's in C):

For the [G7]fiery and the snuffy are a-[C]rearin' to go.

I do it this way:

For the [G7]fiery and the snuffy are a-[F]rearin' to [C]go

Both are perfectly "correct." But I think the F adds a nice harmonic touch to the end of the line.

Some songs are sufficiently simple and straightforward that using any but the three primary chords (or sometimes only two, such as a song like "Down in the Valley") is gilding the lily and doesn't really sound that great. Other songs offer lots of opportunities for alternative chords.

Experiment. Use your ear.

Don Firth