Indeed Schengen visa code does not require nonrefundable accommodations:
- When applying for a uniform visa, the applicant shall present:
(b) documents in relation to accommodation, or proof of sufficient
means to cover his accommodation;
Even proof of accommodation itself is not required, if you can provide "proof of sufficient means to cover his accommodation". A lot of my close relatives and friends had applied for Schengen visa - this includes strict countries like NL and DE - and nonrefundable accommodation was never required.
So what possibly triggered this inquiry in your case? Most likely this is the fact that you booked the accommodation, but once they rechecked it again after issuing the visa, the booking was not there anymore. This made them suspicious that you canceled the reservation once submitting the application, and thus never intended to use it. Which in turn made them wonder whether you're a genuine tourist. Suspicions like that are not good for one's credibility. Thus it was good idea to provide an explanation why it happened, especially if it was not your fault. For example, if the accommodation got canceled because the hotel got overbooked, and notified you of cancellation, this notification should have been sent to Embassy. This would help establishing you as a trustworthy individual who simply got unlucky, and not as someone who's trying to game the system.
Of course now it is all vain, but for future cases, in this case it might be helpful to provide the following:
An explanation what happened to the initial booking. Even if you think it doesn't look good, absent this explanation they'd imagine something way worse - for example that you tried to provide fake documents. Comparing to that if you say "I was sure my visa is denied and decided to cancel so I wouldn't lose money" sounds much better.
A new booking in a similar type and class of accommodation. I would book directly with a hotel and not with booking.com as it is much easier for the Embassy to verify your booking shall they decide to do so.
Other proof that you have "sufficient means to cover his accommodation" - such as credit cards with balance, bank statements etc. As Tom said in comments, if you switch the hotel from $90 a night to $20 a night, the consular officer might wonder what change of circumstances you had during the processing time (got bankrupt? lost job? sued in court?), and thus it is better to be proactive and prove that your financial circumstances didn't change.
Regarding how to proceed? You can apply for a new visa, but make sure this time your application withstands extreme scrutiny. Probably better to visit some other countries first.