When my daughter didn't know I nearly gave up the quest, but just on spec I asked my wife this morning, and...

Mad-Eye never took the map. It was Snape who took it off Harry, but Snape didn't know what it was. Then Lupin came along and recognised it immediately, being one of its creators. He got it away from Snape and kept it until he left Hogwarts at the end of the book, when he gave it back to Harry.

That's wives for you.