OK, here's my last thought. You know so much about James and he tells us he was born in Hoddam and his parents were William and Janet. Could it be that he was known by his second name?
I just tried searching Scotlands People Hoddam male births for Johnston / traditional soundex, with no christian name specified, between 1858 and 1860, and there are 7, of which you already know the details of the birth for James.
I realise its a very long shot but it's about all I can think of. Earlier I got quite excited by finding a James Johnston of the right age, with parents William and Janet, in the 1861 census but he was born in Kirkcudbright so that doesn't seem to fit either!
The Hoddam names are:
1858: Robert Johnston GRO 829/00 0012
1859: Andrew Johnstone GROS 829/00 0044
David Johnstone GROS 829/00 0039
George Johnstone GROS 829/00 0007
James Johnstone (the one you know about) GROS 829/00 0026
Thomas Johnstone GROS 829/00 0042
1860: William Johnston GROS 829/00 0038
They are the only Johnston/Johnstone births I can see in Hoddam for those years, and to check for parents names / mother's MS for all of them would cost just over £7. If none of those are the children of William and Janet it really does look as if your James's birth wasn't registered in Hoddam, even though he is sure it was.
Sorry I can't be more help