About the fsync() problem, I wonder if tagging every write operation with a sequence number (one sequence number per device) would be a good solution:
The device driver can re-order any write with the same sequence number.
Each time a fsync() is done, it increment the sequence number of that device by 1.
Maybe a function call wait_until_current_sequence_number_reached(device);
Wouldn't that be a good and simple compromise?