I got back from a trip to RIM in my LR/D110, with XR650R on the back, a week ago. I don't know what the 'new road' is you refer to, let me know & I may be able to answer. We did NDB-Nouakchott-Atar-Choum-NDB.
„h Border crossing: On the way down we followed the old spanish road, this caused us delays and we missed the 3 checkpoints going into NDB! (N21 03.5 W17 01.4 & 2@ N21 01.8 W17 01.8) On the return, from leaving NDB, to being on Moroccan tarmac, having completed all formalities, took us 2 1/2 hours. That was for 2 adults, 2 kids and the 2 vehicles mentioned above. I guess it may take 1/2 an hour longer for 4 vehicles. We drove way past Dakhla before we stopped to camp.
„h Fuel en-route: We had about 600km range on the piste (plus I could go for fuel on my XR if we ran out in the LR), so we didn't look for fuel apart from at proper fuel stations. One exception to this was at Choum, where we filled up from jerries before the 459km drive back to NDB. I think the distance between fuel *stations* on the Dakhla-NDB leg was about 360km. On the NDB-Nouakchott leg it was about 282km to Nouamghar, where Chris Scott mentions petrol in his book (but we didn't look) and a further 145km to Nouakchott. You need the park permits from the park office in NDB (N20 55.0 W17 03.0), they are now regularly checked.