I tried practically everything that I've heard about the solution for the async workflow issues.
Restarted the Microsoft Dynamics CRM Asynchronous Processing Service
Restarted the rest of the CRM services
Restarted the SQL Server service
Restarted both CRM application server and database server
Went through several blog posts and forum thread related to that issue. (like this, this, this, this and this)
The earliest time of the system jobs being stuck in that status was also some how coincident with the server restart after Windows security update on last Sunday so that we tried to uninstall those updates as well.
We also encountered the following error message when we try to restart the async service "Error 1053: The service did not respond to the start or control request in a timely fashion" so that we even thought about installing async service in another machine as a server role.
And finally, I've found the root cause of the issue after trying out different things.