I am wondering if perhaps he was a grandson of William M and Ann Gordon who were married in 1838, rather than a son? It wasn't unusual for an illegitimate grandchild to be brought up by its grandparents, under the impression that they were his parents.
Ann McKenzie or Gordon, mother's maiden surname Collie, died in Cromdale Inverallan and Advie (CIA) in 1897 aged 89. If her age is accurate she was born in 1807/1808, and would have been too old to become the mother of Henry William in 1869.
She's in the census in CIA
1841: aged 33, with husband William, aged 51, and four more McKenzies, two of whom are too old to be hers - so she was probably a second wife.
1851: aged 42, born Knockando, with husband William, aged 60, born Boharm, a son too old to be hers, four children of her own and a grandson.
1861: not found.
1871: aged 62, widow, with grandson Mathew Allan, 4.
1881: aged 72, with grandsons William J, 13, and Alexander B, 11, both born in Staffordshire, England.
1891: aged 82, with daughter Annie McKenzie, aged 50, married.
Don't worry too much about CIA sometimes being listed under Morayshire rather than Inverness-shire. Until the rationalisation of boundaries in about 1890 bits of CIA were in Inverness-shire and bits of it in Morayshire. I've never managed to get my head round which bits were in which county!
John Gordon and Christian Collie had four children baptised in Knockando between 1798 and 1805, then another one in CIA in 1811. So it looks as if Ann's baptism isn't on record but she is probably another of their children.
William John Mackenzie, mother's surname Mackenzie, was born in Walsall and registered in the March quarter of 1868. The birth of Alexander Bruce Mackenzie, mother's surname Mackenzie, was registered in West Bromwich in the December quarter of 1869. In 1871 John McKensie, 30, born Scotland, is in Walsall with wife Annie, 30, born Scotland, and sons William J and Alexander Bruce. Looks as if John and Annie married in Birmingham on 5 September 1867.
In 1841 the sons too old to be Ann's are Alexander, aged 19, and William, 17. There is a baptism of Alexander to William McKinzie and Elspet Gordon on 20 September 1821 in CIA, and a baptism of a son William on 31 January 1824. William M and Elspet G were married in CIA in 1821.
None of which gets us any closer to finding the record of Henry William's birth.