Firstly it's important to be aware that normally only some nationalities are able to obtain visa-on-arrival visas for most countries that offer them, so before even considering using them you should confirm that you are eligible. If you are from a country that is not eligible for a visa-on-arrival, and you attempt to board a flight without a visa, then you will be denied boarding.
As far as being denied the issuance of a visa-on-arrival, this realistically very rarely or never happens.
Countries issue Visas for a number of reasons. The first is that they use the visa as an opportunity to pre-approve the passenger to travel to their country, and to be able to be able to carry out certain activities when they are there (eg, tourist only, carry out business, work, etc). This is basically the "intended" use of a visa, and visas such as this are always issued in advance, and normally only after providing significant details of your background, previous legal issues (arrests, charges, jail time, etc), details of what you intend to do in the country, etc.
Countries that issue "Visa on arrival" visa to certain visitors generally do not go through this background check process, and instead simply issue you with a visa immediately - meaning that the chances of you being 'rejected' are extremely low.
In many instances, the only reason that these countries even issuing visas in situations like this is money - they charge you for the visa, but do basically nothing in return.
For example, most nationalities can visit Turkey without obtaining a visa in advance, and simply obtain one just before going through immigration. For a fee of between US$20 and US$60 (depending on your nationality) they will open your passport to a random page, apply a "visa" sticker, and then hand your passport back. At no time do they even open your passport to the information page or ask any questions when "issuing" this visa, so there is basically zero chance of being rejected for such a visa.