Advanced metering infrastructure (AMI) initiatives are a popular tool to incorporate changes for modernizing the electricity grid, reduce peak loads, and meet energy efficiency targets. There is the looming issue of how to communicate and handle consumer data collected by electric utilities and manage limited communication network resources. Several data relay points are required to collect data distributedly and send them through a communication backhaul. This paper studies the smart meter message concatenation (SMMC) problem of how to efficiently concatenate multiple small smart metering messages arriving at data concentrator units in order to reduce protocol overhead and thus network utilization. This problem needs to deal with the added constraint that each originating message from its source may have its own stated deadline that must be taken into account during the concatenation process. This paper provides hardness results for the SMMC problem, and proposes six heuristics and evaluates them to gain a better understanding of the best data volume reduction policies that can be applied at data concentrators of AMI infrastructures. These results are further tested for feasibility under practical settings based on aspects, such as network and processing delays, tightness of application deadlines, and lossy backhaul links.