Elizabeth also seems to have been much younger than him (aged 15 at marriage!)
When he remarried in England, did he say he was single, widowed, divorced...?
In 1899 Louisa Helen's marriage definitely says she was married with consent of parents (her husband was of age), so who gave that consent if her father was in the UK and not using his original name?
Aside from Ada, the other witness was a William Henwood May. The only immediate references I can find to him are two baptisms to William Henwood and a wife Elizabeth, which both took place in 1895 although one child was born in 1892:
https://www.familysearch.org/ark:/61903/1:1:2MK8-8HFBorn 13 Dec 1892, Isabella Maud, residence given Dundee
(marriage when she was 18:
https://www.familysearch.org/ark:/61903/1:1:KDCP-FJS gives "mother's consent")
Born 16 Jun 1895, Walter, residence given Nodies/Hodies Bay, Transvaal
The possibility arises that William Henwood's wife Elizabeth was Elizabeth Rust - she would have been around 44 years old when Walter was born.
Having trouble tracking down a marriage for William Henwood - a possible brother would be Paul Henwood May who
All the following were registered with mother's maiden name Henwood
William registered Sep 1845 St Germans
(may well have married an Ellen in
https://www.familysearch.org/ark:/61903/1:1:KDC2-11F )
Mary Jane May registered Sep 1847 St Germans
(possibly died before 1851 census)
Rebecca Goyne May registered June 1849 St Germans,
(married 1864, age is wrong but parents Benjamin and Honour are witnesses:
https://www.familysearch.org/ark:/61903/1:1:KDCK-FGV )
Susan Elisa May registered March 1851 St Germans
(married 1873 Durban:
https://www.familysearch.org/ark:/61903/1:1:KDCK-VL2 )
Paul Henwood May registered March 1852 St Germans,
(married 1878 Durban:
https://www.familysearch.org/ark:/61903/1:1:KDCK-LD6remarried 1898 Durban:
https://www.familysearch.org/ark:/61903/1:1:KDCL-MB3 )
Isabella May registered Jun 1854 St Germans
(married 1878 Durban:
https://www.familysearch.org/ark:/61903/1:1:KDCK-FPD )
Samuel John May registered March 1859 St Germans
(married 1882 Durban:
https://www.familysearch.org/ark:/61903/1:1:KDCK-GR8 )
In 1851 they are in St Germans, with William, Rebecca G, and Susan E in household:
https://www.familysearch.org/ark:/61903/1:1:SGKJ-R63Benjamin May and Honour Henwood married March 1845 in Devon.
Aha! Now I have a connection.
Rebecca May (possible sister of William May aka William Henwood May), had a daughter Hilda Constance King:
https://www.familysearch.org/ark:/61903/1:1:2MK8-628The second witness at Ada's marriage in 1904? Hilda Constance King.
So I think there must be a strong connection between the May family and the two Paddock girls.
Finally I found this possible reference to an estate file:
DEPOT NAB
SOURCE MSCE
TYPE LEERS
VOLUME_NO 0
SYSTEM 01
REFERENCE 36309/1943
PART 1
DESCRIPTION MAY, ELIZABETH LOUISA BOTHA. (WIDOW).
STARTING 1943
ENDING 1943
There's also a reference to the possible death of William Henwood there:
DEPOT NAB
SOURCE MSCE
TYPE LEER
VOLUME_NO 0
SYSTEM 01
REFERENCE 21/16
PART 1
DESCRIPTION MAY, WILLIAM HEUWOOD.
STARTING 19040000
ENDING 19200000
REMARKS NO DEATH NOTICE. DATE OF DEATH FROM ESTATE COVER.
If this is Elizabeth, then you can contact EGGSA to try and get a copy:
http://www.eggsa.org/index.php/en/search/help-faqs/384-archive-documents-photographs