I'd go big on that cleaning. Time, super hot water (I'd heat it to 160 in my hlt before adding it to the keg with PBW) PBW, and I'd even go 2 kinds of sanitizers. I find Iodaphor works a bit better on the nastier nasties then Starsan, so I'd use Iodaphor first then finish, rinse, and then you starsan.
Also, break the whole keg down. Completely. If you have a very thin pipe/line/tubing scrubber, use it to scrub out the dip tube, after you let it all soak in the very hot PBW mixture. Every seal should be replaced, every post removed, broken down (remove poppits) scrubbed with a toothbrush and soaked in a super hot PBW mixture. Let it soak for a long time. Overnight in hot water, then dump, rinse and repeat if it's still smells funky. Also, like Tre9er said, use a keg brush and elbow grease. Don't miss anything.
Sounds like a lot of work, but it's worth it to me for peace of mind.