A record cleaning machine such as the VIP 16.5 is well worth it! The 2nd best investment I made (the 1st was buying decks).

I use a Mofi Fidelity brush with L'Art du Son cleaning fluid on a VPI 16.5. The records come up a treat. If that doesn't work then I use slightly diluted Isopropyl Alcohol, let it soak for a few mins, clean it off and then another round of the L'Art du Son.

Not tried any of the unconventional methods yet.