Why do Type II Restriction Endonucleases cleave at palindromic sequences?
Short Answer


  The palindromic symmetry of the restriction site allows a dimeric
  enzyme to bind the DNA in a manner that bends the double helix in a
  way that facilitates the endonuclease reaction.


More Detailed Answer

The ‘palindromic’ nature of the recognition/cleavage site of restriction endonucleases, such as EcoRV (illustrated here) results in a form of symmetry (A) that allows a dimeric enzyme — that forms a tunnel — to bind symmetrically at that site in the DNA (B).

This binding causes the DNA to bend (C) bringing a catalytic magnesium ion into a position in which it can interact with phosphate of the phosphodiester bond that is being cleaved (D). (The dimeric nature of enzyme allows force to be exerted at two points, to produce the bend. Compare bending a thin pipe over one’s knee, applying equal force with both hands.)

Methylation of the adenine nucleotide in the recognition sequence prevents hydrogen bonding of the enzyme to the DNA. DNA lacking the recognition site is not cleaved by the restriction enzyme because it does not bind specifically to the protein so that the magnesium ion remains too far away.

Reference

This answer is based on chapter sections 9.3.2 and 9.3.3 of Berg et al., which is available online at NCBI Bookshelf and is well worth reading in full. There is also a PDB Molecule of the Month item on this, although unfortunately the bending of the DNA is not apparent in the images there.

Comment on Last Two Sentences of Question

There is no particular “advantage for bacteria”  other than “it works”.  So I think the last sentence is looking at things from the wrong perspective.