The painters are right. You can't just paint over rust in a car and expect it to last. You need to remove the rust first. Same as the chalking in your paint. The paint should be stripped back to the wall surface as much as possible, treated with some sort of primer then painted with top coats.
A quick Google comes up with this...
http://www.resene.com.au/homeown/probsolv/chalking.htm
Stewie