What was Arthur’s year of birth, and do you know his parent’s names? This might help in the search.
As you probably know, the Statutory registers on SP start at 1855, so if you believe he died before 1861, you have a small window to find him there. Prior to that you only have Church Records which don’t provide as much identifying or useful information.
A couple of thoughts .... Do you have Mary in the 1861 census and was she a widow? If not, have you looked for Arthur in the 1871 census in case he was just missing from the 1861? Depending on what census you are looking at I know the transcriptions of Scottish census on Ancestry can be a bit hit and miss, often with odd spellings - unsure about others, but you might need to be creative in your searching - looking for first names only, places of birth, other family members etc.
Do you have Mary’s death and burial? Is Arthur with her?
Regarding the surname, have you also searched for Clarke? Maybe search for Cl*rk* to catch variations in spelling. Maybe consider broadening the area when looking for his death as he may have died away from home.