My feelings is that it is down to image control. If you can guarantee you are getting the Altiris client with any new PC then the rest falls into place. This can be done at factory with a custom image (well it can with Dell, i expect other manufacturers have a similar setup). For migrating to using CMS then its managing to get the client on every machine and this depends how homogenous your environment is. For smaller environments with less techies and people that are inclined to follow set procedures you will have more success in maintaining an accurate database by deploying standard images. Large places, with multi sites and many techies who like doing things their own way will struggle more.
At EoL you have the same issue - a small site could manage decomissioning with a procedure, we had a VB script on our build that disjoined from AD and Altiris. Once again, its really what you want and what you can achieve depending on your size and the ease with which you can adopt new procedures.
So we dont have or need a process for getting PC's into Altiris since the client is on the build image and will report in once connected. Once it disappears you have a number of options depending on how much control you have or want over your environment. I've made up plenty of reports which show how long PC's have been missing for but I imagine on the size of estate you have it's unlikely you will pursue things that disappear for a month at least and most of the ones that do turn out to be broken clients or some configuration issue.
I would refer to management and stick down your main goals for having Altiris and never lose sight of those goals. They will direct how you use the tool, for there are many ways :)