Had a similar issue. Spend weeks debugging a process, adding logging metrics, making graphs to figure out where the performance cliff was in an email sending service. The results were so weird they were unexplainable.

Someone suggested just nuke it and bring it back up on a fresh instance. Problem was gone! Everything running smoothly again..