Carbuncle's Ruby does still drop in Valkurm Dunes, and can actually drop from pretty much any leech in the old world zones. They actually even raised the drop rate awhile back, so it's odd that you haven't gotten one yet.. unless you already have one hiding somewhere.

Try typing in-game: /itemsearch "carbuncle's ruby"
It should tell you if you have one and which bag it's in if you do.