Techniques for supporting invocations of the RDTSC (Read Time-Stamp Counter) instruction, or equivalents thereof, by guest program code running within a virtual machine (VM), including guest program code running within a secure hardware enclave of the VM, are provided. In one set of embodiments, a hypervisor can activate time virtualization heuristics for the VM, where the time virtualization heuristics cause accelerated delivery of system clock timer interrupts to a guest operating system (OS) of the VM. The hypervisor can further determine a scaling factor to be applied to timestamps generated by one or more physical CPUs, where the timestamps are generated in response to invocations of a CPU instruction made by guest program code running within the VM, and where the scaling factor is based on the activated time virtualization heuristics. The hypervisor can then program the scaling factor into the one or more physical CPUs.