Hi Karen,
You can have a look at the Wikipedia entry:
http://en.wikipedia.org/wiki/Soundex
Basically, Soundex
-discounts the vowels (which makes sense, because vowels vary all over the map from one region to another)
-uses the initial letter as an obligatory presence (annoying, because it is often the illegible fancy capital letters at the beginning that get mis-transcribed)
-assigns a numerical value to the remaining consonants supposedly according to their phonetic similarity (I would argue very strongly against the grouping, which doesn't take into account many ways sounds are known to vary-- just look at group 2, which basically includes everything but the kitchen sink...)
-the initial letter and the first three letter codes are what Soundex looks at. Two adjacent identical numbers are collapsed into one.
So...
Mcmillan > M254
M- initial letter
c-2
m-5
l-4
Mckinlay > M254
M- initial letter
c-2
k-2
n-5
l-4
The adjacent 2's become just one 2
In this case I would argue that
Mc is just a prefix and the actual surname starts with the following letter. The "initial"
K in (Mc)Kinley should not have been permitted to collapse into the final
c of Mc.
I looked for years to find my great grandmother in the 1850 census. They were indexed as She
lman, instead of She
rman

You can see how they would have different Soundex codes, since r and l have different numbers. This, although there are many many languages of the world that don't make a difference between the two sounds
That said, according to the system Fraser and Frazer
should be the same Soundex code... so I don't understand what was happening with Annie's search! Sounds like the Soundex is not even following its own rules!
All the best,
Sarah