Ok, there is a lot of solid advice in this thread, but also a lot of speculation and vagueness. No one has actually given a specific cause of the problem, or how to fix it. But all the layout advice is good, regardless.
Well, everyone is taking about frequency like its a big deal. It's not, in this case. This isn't a sine wave. The slew rates of MOSFET switches is not even a little related to how often you switch them.
Anyway, I'm going to go all in and give a specific answer: it's your input capacitors. The high dV/dt loop will have ringing voltages superimposed on your switching wave form, and you have easily 10nH of loop inductance there, more than enough to cause >8V of ringing. 12V+ >8V = blown output MOSFETs. And that is indeed what you're seeing, the switcher works at first but as spikes on switching node hammer and quickly blow the FETs, they get more and more leaky, the output voltage falls, and eventually they can't even turn on anymore. The 30mA draw is almost certainly the gate drivers trying to turn on the blown FETs, but there is just one big hole in the oxide layer separating the gate, so it's just shorting through to ground. Whoops.
When the data sheet says the input capacitors should be as close as physically possible to the input of the chip (which, by the way, the data sheet does) what it really means is this: the input capacitors should be as close as physically possible to the input of the chip.
The frequency is not the issue at all here, as mentioned earlier. The MOSFET turn on time is the same regardless of if you're turning it on 50,000 times per second or 500,000 times a second. The switch node formed by the MOSFET drains has no series inductor there. The drains are shorted together to form the SW pin. Frequency is irrelevant. The dV/dt is independent of frequency.
The primary switching loop that sees all the actual switching and (being MOSFETS, very different beasts from, say, a BJT based switcher like the lm25xx parts) extremely high dV/dt slews is a loop from the input capacitors, to the sources of the top side and low side switches, with the drains connected to the inductor. The inductor itself is not actually part of this loop. The two switches wiggle it's one terminal between them, pulling and returning currents from the input capacitors. The input caps are the most critical part of the buck convrter. Output capacitors only effect output ripple, and it's not terrible if they are relatively far away. Parasitic inductance in series with 4.7uH inducantance is just a little more inductance to store energy in, it is not really an issue. The position and loop size of the input to output is mostly DC save for the output ripple, and it should not be a focal point.
Though aluminum electrolytics are not capacitors at 500khz, too much ESL due to their physical construction. They're expensive resistors. They will just have ripple current proportional to their ESR flowing in and out of them, so serve no purpose beyond generating heat. They have far too much ESL to do anything at all to a 500khz ripple. So I assume they must be to heat the board, though it seems resistors would be a cheaper and more reliable means of doing this.
Also, be sure to have enough ceramic output capacitance to keep the ripple voltage low enough that the ripple current on electrolytic output caps (which is simply the ripple voltage/their ESR, since remember, they are resistors at this frequency) does not exceed their maximum. Generally 75mV is the rule of thumb for this.