May Season Update:
Despite the Bad Luck Albatross and Altruis the Outcast nerfs, the deck, with some changes, was still decent enough to take me reasonably comfortably to Legend within a day. The win-rate has dropped a bit and is now hovering in the low 70s.
Games consisted of mostly quest Mage (still strong, but thankfully a bit slower), a nasty discard Warlock deck and pirate and armor Warrior antics.
Despite the quick nerfs to Demon Hunter, I had good results with this Baku version, scoring close to 80% on Legend rank.
Mulligan is pretty straightforward, with many 1-drops to get the momentum going. Glacial Shard works well freezing your opponent or his minions in mirror matches. Consider keeping Bad Luck Albatross in your hand against Warlock, Priest and Mage in case of Reno. A final clever tech is the addition of Cobalt Spellkin. Currently DH only has two 1-mana cost cards; Mana Burn and Consume Magic, the latter of which makes quick work of taunt minions (or cycles).
Good luck grinding to a 1000 wins!
Update 14/04: After the umpteenth Mage broke my 10 game win streak, I wanted to post the latest results.
A good number of games later the win rate has not changed much. Statistically, odd-Paladin has proven most difficult, but the vast majority of "experiences" involve Mage. I've ran the same list and feel quite happy about it. The only cards up for debate are the pirates, as drawing Patches the Pirate before the others feels frustrating.