Does this sound correct?
Can be correct, but where I am it would be awkward.
More for the company than for your or your colleague. (see below)
No other company I've been with would think it's correct to apply for reimbursement for something that the employee didn't pay for.
That is correct. The solution is that your colleague invoices you for your share of the accomodation (or gives you a receipt that you did reimburse them). That paid invoice is the proof that you did pay, and it is the basis for your reimbursement claim against your company.
Legal details may be different depending on legislation, but here in Germany, a private ("natural") person can write an invoice just like a [small] business.
The only thing is: as they don't have a VAT number (like small businesses), there will be no VAT decared on the invoice, i.e. it gives the gross amount only.
I've had a similar request from an employer's accounting/travel reimbursement office: my car was parked at their hotel parking lot so the fee ended up on their hotel bill. My accomodation was somewhere else and didn't have a parking. Accounting said that for the sake of consistency they reimburse all car-related expenses to the owner of the car, as they don't like to have a "loose" parking fee without any other indication that the collegue has a car.
The invoice/receipt in this case was a letter written and signed by colleague and me explaining the situation, giving everything that needs to be given on an invoice (in that case: small amount invoice only), and my colleague signing that they had received the amount due. We also attached a copy of the hotel bill "just in case" (administration is best faught with their own weapons: paper).
With that, you, your colleague and your company have all the paper trail needed for proper accounting, and you should also be fine tax-wise.
What makes this awkward for the company is: as the invoice your colleague gives you has no (cannot have) VAT on it, the company looses its ability to get VAT reimbursement which is a totally unnecessary expense/loss as it could be avoided by reimbursing your colleague for the full amount, and then internally splitting the expenses as appropriate to different projects or internal accounts (which again needs a bit of paper, e.g. you declaring on your reimbursement request that you shared accomodation with was paid by colleague.).
In future, if you want to become friends with the accounting department, you try whether the hotel can give you separate bills.
There may also be a bit of administration psychology going on here: the accounting department trying to teach you a lesson that you better immediately do what they say and how they say - otherwise they'll create lots of unpleasant work for you.