How can I determine when the last time a specific computer requested (or checked for) a policy update from the NS without checking the agent on the client computer itself?
You can check a single asset by just right-clicking on it in NS and selecting Resource Manager. In the Summaries tab you can then drill down to Resource Manager > Resource Summary, and then in the right pane under Altiris Agent Details, you will see when the agent was First discovered, Last Configuration Requested, Last Inventory Received and Last Event Received times.
For a fleet wide inventory report, go to the "Reports" tab in NS and under Notification Server Infrastructure, Agent, Altiris Agent Inventory you will see a number of reports, notably "Altiris Agent basic inventory (no update N days)" and "Altiris Agent basic inventory (sorted by last update)".
For a fleet-wide Configuration Request report, a few items below you will see Configuration Request node. In there you will see a number of other reports, notably "Clients with no configuration in last N days".
Another report that may be useful is the "Configuration request statistics by time" which may be useful in analyzing the peak times and traffic due to your current policy configurations.