Symptoms

Task emails from the workflow which is supposed to be received immediately is getting delayed by hours sometimes days.

Diagnoses

 It is always recommended to update the K2 version to the latest, this will ensure you get the most recent bug fixes, new features as well as enhancements.
In every version released by K2, performance enhancement is always among the list. The current version by 4.6.9, is no longer supported for any code fix related requests. 
Please see support policy explained here: http://help.k2.com/k2releasestrategy.
Also, the list of issues fixed, enhancements and new features in the subsequent releases are explained respectively below:
 - 4.7 http://help.k2.com/kb001745 
 - 4.6.11 http://help.k2.com/kb001735 
 - 4.6.10 http://help.k2.com/kb001700
As for the Delayed task notifications: this is caused by some messages are stuck for long time (back in May) that are still occupying space and attention on MSMQ. Since there is a delay of few hours for task notifications, it is recommended to purge all queue messages at the very beginning of the business day or after a weekend.
This means that any valid message is already processed and the remaining ones will remain stuck in the queue and can be safely deleted. If MSMQ messages still delayed after the clean-up, involving the system admin or Microsoft support to investigate further might be required. Lastly, changing the queue from public to private would be the last option.
Some of the errors related to MSMQ dated back in May:  The queue does not exist or you do not have sufficient permissions to perform the operation.  A queue with the same path name already exists.
Resolution
 

Resolution 
It is recommended to update the K2 version to the latest, this will ensure you get the most recent bug fixes, new features as well as enhancements.
In every version released by K2, performance enhancement is always among the list. The current version by 4.6.9, is no longer supported for any code fix related requests. 
Please see support policy explained here: http://help.k2.com/k2releasestrategy.