Not long ago we had a debt releif order put in place to clear our debts so we could get credit,
I think you misunderstand what a Debt relief order does.... It only removes the need to pay a previous debt back.
It does NOT mean you will get credit going forward.
Anything that requires a credit check will flag your DRO for 6 years. And will have a big impact on getting credit anywhere. Of course companies can make their own judgment call.
Personally, I don't get why Virgin run a credit check. But that is their choice. Maybe it has something to do with the amount they might have to spend connecting everything up.