I realize this won't do you any good as you're in the UK, but in the US, Photo Warehouse (aka UltraFine Online) has a store brand RA-4 paper. I bought some recently, but I haven't yet tried printing on it. I don't know who actually makes it; it's conceivable it's just rebadged Fuji, although the box seems thinner, so I suspect it's got a thinner base than the Fuji paper. I gather that, in addition to Fuji and Kodak, there are two or three other companies still making RA-4 paper, including Mitsubishi and Agfa. I believe Ilford (the ones who do Ilfochrome, not Ilford Harman) also has an RA-4 paper. AFAIK, most of these products aren't normally sold in cut sheets in the usual outlets, but it could be that Photo Warehouse is buying the stuff up in rolls and cutting it down themselves. Maybe somebody in Europe is doing the same thing.
An interesting point and one perhaps worth further investigation in regard to the European market.