You're not mistaken - H2G2 started as 2 radio series on BBC Radio 4 and the books came later. Belgium was used in the radio series. I don't know if the joke was used elswhere before but since Doug Adams also wrote for the Monty Python team briefly he may have got it from there or used it twice
c.f. the line about the long dark teatime of the soul and the Drik Gently book of the same name.
