The first change was in 1862-1863 when the registration district of Cromdale and Inverallan (93) was split to become Cromdale and Advie (93/1), and Inverallan (93/2).
Then in 1869-1870 the registration districts of Cromdale and Advie (93/1), and Inverallan (93/2) did indeed change counties. Both were transferred from Inverness-shire to Moray (becoming RD Nos. 128/b1 and 128/b2 repectively). Other RDs along the Inverness-shire / Moray boundary changed county at the same time.
In 1892-1893, they were re-numbered again, to 128/1 and 128/2 along with many other changes at that time. As far as I can determine, they combined in 1965-1966 to become Grantown-on-Spey registration district (128). That still seems to be a surviving registration office, and probably holds one copy of the statutory certificates for these districts.
I have made some explanation of this in the information pages to be found from TalkingScot's homepage. A chart of all of the county changes that I could find is at the following webpage.
http://www.talkingscot.com/rds/county-changes.htm
Some explanation can be found at
http://www.talkingscot.com/rds/rds-intro.htm
Moray is the the same county as Elgin(shire). Although there is no date when the name changed from Elginshire to Moray, in general, older documents are more likely to use Elginshire and newer documents use Moray.
The statutory birth, death and marriage certificates for all of Scotland are to be found in New Register House in Edinburgh. This is probably an easier facility for you to do your searching as it has the search rooms for that. I don't know the practicalities of searching at the local offices.
All the best,
Andrew Paterson