Doing some searching (basically google://uk wedding invitations recycled/) reveals a few, but it mostly seems to be very small companies (read "one woman in her basement") and what I'd consider overly lighthearted for wedding invitations, but, then, maybe that's the style in the UK.

Another possibility is that you might be able to find a printer who might not have the paper you want, but you might be able to buy the paper separately and have them print on it.