Generally speaking, when it's an /i/ sound that comes immediate after or immediately before another vowel, where the other value is not represented by a letter; however, it remains single in the beginning of a word even if followed by a vowel without a letter. Telling example: the word "pie" (as a type of cake) is written פאי in Hebrew. The mathematical constant "pi" is also written פאי, but some prefer to spell it without the silent א, and then they'd double the yod: פיי. Two states in the US: מיין vs. איווה (note איידהו, though: the א represents the consonant more than the /a/ vowel). The first names ירדן and ירוחם exemplify the exception for word beginning.
The motivation behind this arcane rule is to double in cases where a single yod would tempt one very strongly to read it as an /i/ vowel without the other vowel. If one sees נעלים one is tempted to read it as /na'alim/ (Hebrew being Hebrew, this will quite often be another existing word; in this case it is!).
But in this example, wouldn't you say that the double yud is here because originally this was dual number, while plural would have just one. But since נעלים isn't plural for shoes, נעליים stayed as de facto plural of the word. Unlike examples such as חודש-חודשיים-חודשים.
Well, I would say that because originally this was dual, it's pronounced /na'alayim/ and not /na'alim/; that's a strong fact of how Hebrew speakers speak. How you spell /na'alayim/ is another question, up to experts' decisions and standards. As it happens, with niqqud you'd use one yod.