Well when I tried your code as-is it didn't get rid of the problem.
However, enabling NO_PRESERVE and just destroying and recreating did.
In my main application I have made some progress.
I found out that the problem is occurring in the destroying process that happens immediately after the lost event. Somehow an al_destroy_bitmap() call is failing. This is of course later causing reset to fail.
Right now, I'm using ::al_is_d3d_device_lost() to test if the device is lost in different places. I've figured out that those cases where the device is unable to reset correctly happen when the device is lost INSIDE the display routine (bundles all of the rendering for the application). So even if I skip the display routine if the device is lost (which I am currently doing), it can still happen inside. And somehow that's causing this problem.
Basically, it looks like even if I use the code that you supplied - that uses callback routines - I'll still have this problem. I have to dig deeper to find out exactly where it's happening and if I can do a test when I'm destroying.
I may have said something wrong, but this is the gist of it. The display is lost inside where I use allegro display routines and somehow it's choking something that prevents me from destroying a bitmap.