In recent years, mobile elements (MEs) have been proposed as mechanical carriers of data to prolong the lifetime of sensor networks and to overcome network partitioning problem. A scheduling approach is proposed in [1] for MEs to collect periodically generated data, also called regular messages (RMs), from nearby sensor nodes with no buffer overflow. However, increased delay in message delivery with ME-based communication compared to multi-hop communication may not be tolerated in some cases. Some messages can be more urgent than others due to critical values of the sensed data. Such messages maybe required to be delivered to the ME within a specified deadline. In this paper, this new problem of Differentiated Message Delivery (DMD) considering both regular and urgent message collection is addressed. The proposed solution incorporates multi-hop communication into the ME scheduling problem. The investigated performance metrics are the minimum required ME speed to prevent data loss and guarantee the maximum tolerated urgent message delay, as well as urgent and regular message loss rates for a given ME speed. The proposed solution is shown to perform well in terms of these metrics in various network scenarios. Furthermore, comparisons with existing ME scheduling algorithms show that the proposed solution meets the urgent message delivery requirement with a reasonable increase in ME speed.