The cost of xp increases every time you add an enchant via ebooks (not sure if that's the same with enchantments via the xp store). The cost also increases with each name change.

 

How did you obtain that axe? Did you make it a long time ago with an enchantment table? Did you make it blending two or more axes on an anvil with different enchants (or with the same enchant, in order to get an higher one)?
If you bought it from someone as-is, did this someone obtain it in one of those ways?
On ECC we're used to forget the history of tools because they can be easily enchanted by signs and repaired via command; however vanilla MC allows you to use anvils to do much more than just renaming it (including repairing in the old, xp-costing way), and every time a tool is subject to anvil manipulation, the level needed to manipulate it again, even to just rename it, increases accordingly. That's why tools are unavoidably perishable in vanilla MC (something we're not used to here, at all).
TL;DR: I don't think it's due to a bug, probably your axe has just a very long enchantment_table/anvil history that you forgot or know nothing about.

 

This I don't know, something of the anvil mechanics might have changed since 1.7, or maybe it was already there and I overlooked it, I don't claim to be an expert on MC anvils. But the heart of the matter is that vanilla anvil mechanics is pretty complicated and involves a raise of the XP level needed at some points of a tool's history, at that could be the cause in your case.

 

@JamieSinn is this an issue we need to look into?

 

Currently already looking into. Tied to another issue.

 

Please make sure ticket is made on our tracker.

 

Already there.

 

Any updates on this?

 

Working on a non-intrusive fix for this. Currently a few things are causing it to be delayed.