I don't know if this is still a problem in beta 4, but since it wasn't in the changelog, I guess so.

Sometimes when I've rebooted my computer and execute K-Meleon, all toolbars are in random order. Even when "lock the toolbars" was enabled!

Ditch the loader.

The loader? You mean that little app that boots with Windows and "makes K-Meleon boot faster"?

I didn't have it installed at the first place.
So that can't be the problem.

Mmh, do you sometimes close XUL dialogs using the [X] in the upper right corner? If you do, K-Meleon won't close properly afterwards and will therefore continue to run in the background. Shutting down Windows under such conditions might sometimes lead to the problem you are reporting. Apart from that my toolbars were only messed up one time during the beta - K-M closed itself/crashed.

Oh, did you install beta 3 in a completely empty directory, without using any stuff from your old profile?

I don't remember clicking away a XUL dialog, but it can be. Than that must've been the problem.

I now have beta 4 and not having this problem anymore.