How do you construct a practical full-domain hash function?
I don't know if that counts, but authors of recently selected SHA3 function Keccak mention its ability to perform Full Domain Hashing:


  Variable output length hashing is an interesting feature for natively supporting a wide range of applications including full domain hashing [...]