Your queue server rebooting is completely orthogonal to whether the application submitting the message can do so atomically or not. Use a cloud service if you care about durability.
Edit>> I see you edited your post after I responded. None of those scenarios qualify as "fairly often."