I think the best strategy to make it intuitive would be to flatten the redo stack as a single command, so that the pile of successive 'undo's gets redone as a single step. In your example:

  Type "hello"
  Type "world"
  Type "!"
  Undo
  Undo
  (Editor is "hello", with "world!" on the redo stack)

  Type "dave"
  (Editor is "hellodave")
  (This would normally wipe the redo stack but instead it moves it to the undo stack)

  Undo
  (Editor is "hello")
  Undo
  (Editor is "helloworld!")
  Undo
  (Editor is "helloworld")
  Undo
  (Editor is "hello")