Just had druid quest and the 75 murloc quest at the same time. Put lots of murlocs + the cheap new druid taunts, mark of the lotus and power of the wild in a deck. Went 5-0 and finished both quests in 5 games.
Played a 6th game after quests were done and came up against a token druid deck that played double flappy bird turn 1 to remind me my deck was not a real competitive deck.
Edit: I'd point at the deck at my signature but it wasn't exactly a throwaway deck since i was actually trying to "translate" Murloc Paladin into Demon Warlock using kind of the same theories the Murloc Pala deck uses.
I did quite well with an all taunt except Reno Jackson and Armoursmith warrior to do a taunt quest, had a winstreak completing the quest.
My best one was the no minions costing less than 3 deck which I still play now when I get a priest quest or have the 40g play minions costing 2 or less quest, it's become more like Big Priest these days, but for wild. Still need another Eternal Servitude and Obsidian Statue to improve it though. Only cards I crafted where the obvious first ones when I started, Ragnaros and Sylvanas, all the other legendaries jammed in there were from packs or adventures.
EDIT: I have similar one on my US account, but don't have Y'Shaarj or Kel'Thuzad, nor an Obsidian Statue, but I did open Deathwing and Ysera and added a Free From Amber and that did well today at rank 15 in wild for a priest quest. No one expects the Deathwing unless they see a 1/1 from Barnes ;) They usually kill it and I resurrect a 12/12 though.
I was surprised, and pleased, to see several types of decks I've made to do quests or just fool around with in casual be listed by others.
Like the OP, I made a discard Warlock deck because I pulled the quest and figured might as well. It wasn't great, but won a few here and there. I also made a divine shield paladin deck similar to what Pandabird said. It worked surprisingly well!
I also tried making a few iterations of a Druid quest deck, since I also pulled that back when Un'goro came out. It would either do great or be steamrolled quickly, but the games were fun.
i recently had loads of fun and was actually doing very well in casual w/ a burgle rogue w/ voss and gallywix. used unstable ghoul + plague scientist as anti-aggro/board clear (which people often played right into). the deck felt like it was two slots away from being tier 2.
i also recently had a druid card quest. threw 30 randomish strong druid cards in with little thought of synergy or composition. it was wayyyyy better than it should have been.