@syzygy.
About 6 weeks each time. I think it must be something to do with their financial systems. The blurb that comes with the cheque suggests that the crossword department sends an "invoice" to the accounts department who then, after a suitable delay, act on this and pay up.
Such things are sent to try us! One nice thing, however, is that the cheques are drawn on one of those posh private banks. Not Coutts & Co but of that ilk.