I have been servicing my own regulators for many years. Used to service gear for a dive shop when I was a scuba instructor in the 80s. The level of training aptitude of many of the people who work in dive shops and service regulators generally seems to be low. The manufacturer service courses are no guarantee of competency and some are apparently run on a no fail basis even if they are completed.
Have come across some real horror stories from dive buddies who have tried to get regs serviced, and once myself when I was travelling in Canada. Wrong tools being used, critical parts left loose, regs not actually serviced at all etc. Really unbelievable stuff.
One guy I regularly dive with is a ship's engineer who maintains and repairs really complex pieces of equipment as part of his work. He was told by that he wasn't qualified to service his own regulator by a dive shop sales person who I know did not understand the way his regulators worked.
It is not hard to service regulators if you have a bit of mechanical aptitude. In my opinion it is much simpler, for example, than cleaning a carburettor.
I don't use an ultrasonic cleaner, although an intermediate pressure gauge is essential. Some regs require specialised tools, many don't, although an inline adjustor for the second stage is very convenient for many models.
Servicing your own regs can be fun for some (me) and save you money, especially if you have multiple regulators. If you service your own reg you can also keep track of its condition more easily and fix it yourself when you are on some isolated island or dive boat when the is no shop support.
Given the poor level of service I have experienced and seen I would actually feel uncomfortable letting a shop touch my regulators unless I was absolutely certain they were qualified to do the job. Even then, I enjoy and prfer to service my own dive equipment.
Please excuse the following rant, but I find the restricted access to parts really annoying. There is no justification for this, particularly if you consider you can go and buy brake parts for a truck, car, bus and lots of other potentially life threatening things, and dive shops seem to happily sell regulators and other life support equipment to anyone who has the money (well I have rarely hear of a dive shop asking for a C card before selling scuba gear).
It is good to develop a relationship with dive shops (I have) so you can get service kits, but if this is difficult, the internet can now provide service manuals and service kits for many types of regulators. If you can't get parts form you LDS, consider buying your regulators from another source. Negotiating parts availability when your are purchasing the reg can give you a bit of leverage. Dive Rite has a particularly enlightened view on this and should be supported. Other manufacturers should follow their lead.