Traditional anti-virus (AV) solutions are known for their considerable consumption of resources, limiting their usefulness on the cloud. In contrast, cloud-based lightweight malware monitoring approaches consume fewer resources than a full malware scan would normally require, however, they are often prone to false alarms; limiting their effectiveness. In this paper, such a trade-off is addressed by proposing a prioritisation approach, consisting of two protection layers (i.e. lightweight and full malware scanning) to conduct a scalable and effective malware inspection of the cloud Virtual Machines (VMs). The novel contribution of this paper is a market-inspired mechanism that utilises lightweight scanners to prioritise the AV scanning process, by deciding which VM should be thoroughly scanned and when; it will trigger then a full malware scan on a pre-defined percentage of the most critical VMs. The conducted evaluation shows that the framework provides a cost-effective scanning method, while being able to confirm the infection status of the most critical set of VMs; thus maintaining a low rate of false alarms.