How to protect an application against virtual machine time tracking loss issue?

SCENARIO

We have an app written in Java. It used to run on a physical machine smoothly. The decision to move to virtual machine has been taken. Now, the app presents regularly inaccuraccies in the timestamps of the logs.

ILLUSTRATION

BEFORE virtualization

Timestamp    | Caller | Message
00:00:01.735 |  foo   | Downloading something
00:00:05.123 |  foo   | Downloaded something
00:00:05.123 |  bar   | Analyzing something
...
00:00:08.990 |  foo   | END

As you can see, the timestamp values grow continously on the physical machine.

AFTER virtualization

Timestamp    | Caller | Message
00:00:01.735 |  foo   | Downloading something
00:00:05.123 |  bar   | Downloaded something
00:00:05.123 |  baz   | Analyzing something
...
00:00:04.485 |  foo   | END

Now, the logs state that the process ends during the download.

SOLUTIONS TAKEN

We have synchronized the VM with NTP servers. The issue disappeared for some days. It is back now.

QUESTIONS

• Should we synchronized more often?
• Can we imagine to override somehow System.currentTimeMillis()?
• Should we change the timestamps values in the log based on detected time drift?
• How to solve the virtual machine time tracking loss issue?

Host OS: RHEL 6.5
Guest OS: RHEL 5.4
Virtualization Platform: RHEV 3.4

You have to choose between different options

• Have a precise time with more frequent time sync, but more inconsistencies in timestamp ordering ...
• Have a less precise time by making less frequent time sync, or even totally disable it, but more consistent in timestamp ordering ...

From what I know, it's not possible to have the same accuracy as in a hardware computer.