My partner left voluntarily last year but his airfare was paid by the Govt and then he paid them back within 28 days on his return to his own country (and we have proof) However,we have just had a Spouse Visa application and one of the reasons given was that he was ultimately returned at public expense.
While your partner left a year ago, and without seeing his removal notice, the recent refusal suggests that he may still be affected by the terms of the removal. His was an assisted voluntary removal, at government expense, and while he repaid the costs, the terms of his removal order still would be in effect.
After a removal order, when one is allowed to apply to return to the UK varies, either in 2 years if one leaves within 6 months of being told to leave, 5 years if it takes longer than 6 months (and described in his administrative removal order documents).
With the removal and refusal on his record, you would be better served by consulting a solicitor whom you can locate through the Immigration Law Practitioners' Association.