I would suggest looking at a service bus with sagas (my preference is Rhino Service Bus, but NServiceBus also has a lot of traction, and there's also Mass Transit)
Basically a service bus will handle the plumbing of enqueuing (aka sending) messages, and dequeueing (aka receiving & processing them). A saga will then assist with maintaining state for a conversation (where a conversation consists of multiple messages).
The issues of retrying later can be handled quite elegantly with delayed messages in Rhino Service Bus, and timeouts in NServiceBus (I have no experience of Mass Transit).
I would store the result logs in a database to make it easier to query & report on. I would also rather use a servicebus with MSMQ (or any other queue) than use a database table as a "queue" - the former is designed precisely for your scenario, whereas the latter is a much more generic product to handle many different scenarios and thus it won't be as efficient as a queue implementation (eg MSMQ) (although it can do it - but scaling becomes harder).