I personally have done all the quests in Deepholm and my friend has completed the quests achievement in Deepholm aswell, so I think the situation is the same. I also think that Aeonaxx isn't affected by the phasing.
Deepholm acts like an instance and you don't need any noodle carts here - as long as you stay online, you can go around, unmount, mount, kill stuff, loot and so on. Interesting note - Darkmoon Island acts exactly the same and all the NPC's are there along with the chest for the achievement ^^