Hi, JS Tan:
My approach will be facing machine by machine to see what is happening. What do the machines not working properly have in common (same OS, same SP level...)? May be there is a pattern that can help you in making a diagnostic about possible causes.
Look at the agent logs in those machines. You may find any message related to what may be happening...
Also look at the log in the Altiris server: may be you can find errors there coming from the agents...
Once you have the error message from the log, or you found the common configuration leading to the error, you can search in Connect for something more specific.
Good luck:
Falquian