Multiple-stage system and method for processing encoded messages

System and methods for processing encoded messages at a message receiver are described. Encoded message processing is performed in multiple stages. In a first stage, a new received message is at least partially decoded by performing any decoding operations that require no user input and a resulting context object is stored in memory, before a user is notified that the new message has been received. When the user accesses the new message, any further required decoding operations are performed on the stored context object in a second stage of processing. The message can subsequently be displayed or otherwise processed relatively quickly, without repeating the first stage decoding operations. Decoding operations may include signature verification, decryption, other types of decoding, or some combination thereof.