In our last game, the players worked their way through a series of fiendish traps into a high security vault, where they recovered a Staff of the Magi. After the game I looked at the stats, and realized that (oops!) the staff is massively overpowered for a part of level 2 players. I don't want to just retcon "you thought it was a staff of magi, but it's actually X", because that seems really mean - I've already told them what it is, I don't want to just take it away by GM fiat. So now I'm trying to think up a good in-game way to part them from the staff, which won't feel like I'm taking away their new toy. Therefore my question is:

If I have accidentally given a massively overpowered weapon/artifact to a party, how can I get it away from them without making them feel cheated?