It's always possible to come up with an even worse case that ruins whatever solution you come up with. Assume a hostile web service, or a hostile database, and you're screwed.
But in the scenario you describe, you mainly need a more reliable action log than an external database. Let's assume that the local file system is reliable if you don't increase file sizes (which could easily fail if the disk is full).
Then the program should, at startup, create a small file which contains just two fixed-size records, each consisting of space for an ID and a status flag. In addition, we change the database to something slightly more elaborate: the processed flag can now be "new", "in progress" and "processed".
Then you want something like this pseudocode:
txlog = disk struct { id, status }
record = db -> load record
txlog -> id = record.id, status = sending
db -> processed = in progress, on failure txlog -> clear and start over
web -> send request, on error response goto service error, on timeout abort
txlog -> status = sent
db -> processed = done, on failure abort
txlog -> clear
The service error handler looks like this:
txlog -> status = failed
db -> processed = new, on failure abort
txlog -> clear
Now, the interesting part comes next. If you get a db error and abort, or your program suddenly disappears (power loss), or if you never get a response from the web service (webservice crashed, or connectivity loss), your program will eventually start again and realize that the txlog file is not cleared. Then it needs to go into error recovery mode.
If the txlog has status "sending", check the db record. If that has status "new", your program died before it could send the request. Clear the log and proceed normally.
If the db record has status "in progress", you're in trouble: it means something went wrong at a point where you might have sent the request to the web service and it might have been processed. Maybe you lost power or network, or the web service did, but you can't know whether the request went through. In this case, you can only alert a human operator to take a look. I'll talk about that later.
If the txlog has status "sent", the record was sent. If the db still has status "in progress", then try to set the status again. If not, your program died just before it could clear the txlog, or the db did its update but disappeared without sending a success message. Either way, clear the log and move on.
But what about the error case? This is the "worse case" that I mentioned in the beginning, the real issue of the unreliable system that you're dealing with. Power loss at just the wrong time. A network cable that suddenly gets cut. Your system needs to adapt, and if, as in the case you're describing, it can't (the web service you describe just doesn't give that option), you're screwed if the worst case happens. The process I described will at least alert you to it. The human operator can then perhaps contact the web service administrators to ask them about their logs, or otherwise make an informed decision what to do about the operation that may or may not have been performed.
On a side note, could we design, say, a text message service that is idempotent? Sure. The service would require, as a first step in every process, allocating a GUID for the message to be sent. Once you have that GUID, you can store it in the transaction log. Then you send your message with the GUID. The service can then check its own records and discover that the message with this GUID has already been sent, and therefore not send it again. And even if the web service failed to properly record the fact that it sent the message, the final receiver can do the same - the phone, for example, could see that it already received a message with that GUID and ignore the new one.
