Wow, my Samurai is doing pretty awesome.
Found Medusa's Island, and it's version 2 (meaning that the boots of levitation are much more likely to be on the Statue of Perseus than the shield of reflection) and I headed back up, seeing myself as underprepared.
I headed back up to one of the first floors, where I reentered a shop, and did one of the most boneheaded things ever, I ate a tin in the shop. My hands got slippery and I dropped my excalibur and my +1 katana, which the greedy bastard claimed as his own and then marked up to ridiculous prices! I can't believe I forgot about that. So anyway, to fix this, I just picked up everything of value, including MY weapons, and then read a scroll of teleport. A couple dead Keystone kops later, and I'm off scott free.
Then I found some potions of gain level and I used those to propel myself to level 16, where I then entered the quest.
With magic resistance, the many wands wielded by the japanese guys didn't hurt my one bit as I mowed through them. I found some boots I hadn't seen before, and I got a hawaiian shirt, plus got so many wands and potions that I decided to lock myself in one of the small rooms, and I broke out some more scrolls of identify, blessed them, and I managed to ID all my stuff. Turns out, I picked up a Wand of Death, some speed boots, and a plethora of other stuff. I then blessed the pile of enchant armor scrolls I've been hoarding and used those to enchant my new Hawaiian shirt, leather gloves, speed boots, and elven helmet. Combined with the +5 divine protection I bought earlier, I had -21 AC! That's the best I've ever done. So then I just mowed through the rest of the level, and defeated Takaji-whatshisface with a single shot from my Wand of Death (I accidentally wasted a charge when I accidentally forgot to specify a direction the first time, DOH!) and got the Bell and the Tsurugi of Muramasa, a weapon I'm entirely not interested in.
After picking up the majority of the TON of free potions lying around, I traveled back up and completed the quest, the first time I've ever done it.
I then dropped the Tsurugi of Muramasa into a box near my favorite altar, because I'm very happy with my current setup (dual-wielding excalibur and a katana) and the Tsurugi is taking up weight and has no redeeming value in my eyes. It only counts as a luckstone for crying out loud!
I then bothered to use up the last of my scrolls of create monster and wands of create monster at the altar, didn't get anything. Then I just blessed all my potions of healing and extra healing (but not full healing) and drank them all for the boost in HP.
I don't have boots of levitation yet, but I have something better, a ring of teleport control! I tinned some leprechauns earlier, so at any time, I could just put the ring on, eat a leprechaun, and start zipping whereever I want. Also, I learned the identify spell a long time ago in minetown if I've forgotten it, then I can self induce confusion, read one of my scrolls of teleport, then use teleport control to levelport whereever I want, so Medusa's island doesn't look so well-defended anymore.