My wife and I do approximately 160 dives a year. We get our main regs serviced every two years (roughly). Yesterday I put them in for service as in August we are going to Scapa Flow in Scotland to dive the (deepish) WWI German wrecks. Last time we serviced them was just before we went to Chuuk Lagoon to dive the wrecks which are on average, deeper.
Our other regs (for pony bottles, oxygen and spares) only get serviced every third or forth year. Sometimes they can go more than a year without being used, so no point getting them serviced.
Although my regs are working (apparently) fine now, I know that when I get them back next week they will be much better and this will be obvious.
There is no reason to get them serviced every year. Even for "free" parts, you would be better off dollar-wise only getting serviced every second year.
As to who to get serviced by, this can be difficult. I used to use a dedicated scuba mechanic but I felt that his service dropped off and his price increased. I changed to another bloke who again only does gear servicing. He is reliable, gives our club wholesale prices (he does many dive shops as well) and his work is excellent. I will get them back less than a week after I gave them to him. However, I did check beforehand to make sure that he could do them this weekend as we are away not diving and it is the only time we will not need them for more than four days.
There is now only one dive shop near our house. The person who owns this appears to do the servicing of regs himself. He does not seem to want to employ anyone. As a result, regs put in to him can take 6 weeks or more. Hopeless.