I'm running the latest version of k-meleon (1.5.3) with XP pro, and I'm finding after shutting it down, it's still running in memory (when I hit Ctrl-alt-del together). If I then try to start it up again without killing the task in task manager, it won't start, nothing happens. If I kill the task, and then start it up again, it tells me it was not shut down correctly.

Try to find the error via error console.
Can be anything damaged chrome, skin, pref...

Typical for JavaScript error.

If You cannot find and fix the reason create a new Profile. If that also has the habbit reinstall K-Meleon and create a new profile. private data such as bookmarks and passwords can be transfered, You should do & keep backup.