After suffering a laggy Flash CS4 for nearly 6 months, I finally decided maybe it was an issue with the software and not my file. I feel stupid for not considering this possibility – an update which fixes the problem have been existing for over a year now.
Download it at: Adobe Flash CS4 Professional Update (10.0.2)
30MB (140 for Mac) and doesn’t require a restart.