I generally write a new editor for each game I make, completely tailored to
the game.  My first pygame project was so bloated and focused on "making the
ultimate engine that can do everything and has an awesome editor" that I
just never got around to finishing the game.  Ever since then I have been
having a blast doing everything I can not to run into the same rut :)

A shoot 'em up I was working on uses a web-based editor that edits a
database full of all of the game stats, which is a really nice way to be
able to tweak stuff quick without even having to load the game.  The last
contest game I made has a really bizzare but quick to use editor.  Heh, it
was really strange because every action you did would save and then execute
the function.  So the "level" is just a saved queue of function calls.  Each
function knows how to undo itself, so when you load a level, you can still
undo all of your actions one by one.

There is definitely a lot of innovation you can have beyond just tile
editing and object placing in an editor.

Actually, about recording, I used that in my shooter game to record boss
scripts, it worked pretty well.  I think an ai editor would be a really nice
feature to have, but you kind of have to have a nice ai engine to go along
with it.

For the record, most of my editing functions are in-game editors rather than
seperate tools.  Need to fix a tile or move the starting location?  Just
pause the game and away you go.  But it really depends heavily on the game.