We have used frontline on Rocky since we got him. (Usually in the summer only because I really dont like the pesticides.) With the exception of when we got him with fleas we have never seen one on him yet.
I'm not sure about the all natural stuff but the hartz stuff is dangerous. I've heard and seen so many horror stories about that crap, especially if you have cats. I worked at a vets office briefly and saw numerous dogs come in with severe reactions to that stuff.
I have used diatomaceous earth. the thing is, there are no residual effects. It does not repel, but kills the fleas that are there. I also mixed lavender, eucalyptus and citronella oil in a little water, and sprayed it on daily. Same as above, none of these treatments have residual effects. The essential oils repel the fleas, the diatomaceous earth kills the ones that make it past the oils.