With virtual servers, a common issue is with sharing the blade with other high I/O servers. In your case, the blade consists of a Domino server and a Traveler server, so any contention for I/O should be easily seen.
Do your users replicate their mail locally? If so, they would be fairly well insulated from any blips in server performance. Your users might also benefit by using server-based archiving. Archiving all but the current year of mail should result in faster response when working in their mail file. The older mail would still be available to them.
I would run Performance Monitor on the server during business hours for a full shift to see if there are any spikes in activity. You can also check platform statistics in Domino (for example, sh stat Platform.LogicalDisk.1.AvgQueueLen.Peak*). The stats that end in PctUtil.Peak like Platform.PagingFile.Total.PctUtil.Peak might be useful in identifying possible bottlenecks.
I would say that 8 GB RAM and 4 CPUs would be a minimum for a Windows server hosting Domino or Traveler.