The further you go into the 20th Century, the harder it becomes to search unfortunately on line.
You no longer have the benefit of IGI (as you know, this stops around 1874). The current last census available for Scotland is 1901 (the 1911 Scottish census will help you but not due to be released until Spring next year).
To go on a fishing expedition on SP for a common name without any further info gets mighty expensive as I am sure you are finding (units disappear into puffs of SP smoke!). You are also going to begin to be restricted on SP with what images you can view on line (births currently to 1909, marriages 1934 and deaths 1959). You then need to order those certs which fall outside of the on line viewing periods. Does get frustrating
From what you have said, being overseas means you can't pop along to a genealogy centre in Scotland where you can view more 'modern' certificates on line there.
Some of the things that people try, you are already doing (checking for entries with middle names, looking at deaths with mother's maiden name etc). You can also check for births where they may have used family names for their own children with known surnames as middle names which are frequently used in Scotland as you are finding.
Other things to check for are whether they appear as informants to family deaths or witnesses to siblings' marriages but I'm not sure if you know the names of other siblings and, from what you have said, father and mother died early.
I don't think you know whether he married and if so, wife's name. Married women's deaths are easier to search for on SP as you can search for both maiden and married surnames. If you find the right entry, you can find out if spouse is alive or deceased at the time of wife's death, which helps narrow down the time frame for your searches.
Not sure whether any of these suggestions may be of use to you
Hard search.
Monica