Removed in 4.0.1? Edit
I received this tooth today (11/26/2010) on patch 4.0.3a despite it supposedly being removed.
Kraken has gotten very easy to kill... the spear dishes out ~100k damage per throw. I killed Kraken myself twice on a flight now. But no tooth. Is the quest removed?
It has been removed. Killed it three times and no tooth dropped. I have edited the main section to reflect this, but I am not sure if it was the right place this information should go.