Travel exhaustion apply three effects movement decrease, spell failure and attack penalty those effects should be removed after using a lesser restoration or Restoration or Greater Restoration, but they don't remove the effects, it sems that the effects that exhaustion apply to the player character is not Magical (i know magical can be removed with dispel but still you spend something to remove the effects will be the same think) but Extraordinary that's a bug should be able to be removed. Based on PnP 3.5 rules.