Yes, this has been my exact experience from the beginning of the whole Continuity rollout. As much as I wish it wasn't the case, Apple still has a ways to go with their cloud service stability.
I don't think iMessages are ever stored in the cloud; they're queued for delivery to any device registered to use the ID/number the message is sent to, then deleted.
This is why, once delivered, there's no further synchronisation. Of course, they could give each one an ID and then push a "delete iMessage ID nnnn" message to each device when you click "delete" on one, but I guess they decided not to bother.
How do I fix it so that Messages is synced on both my iPhone and Macbook??
Do you have the same "You can be reached by iMessage on" setting on both devices? Maybe one is using a phone number and Apple ID whereas the other only an Apple ID, and your un-sync'd conversation is going to the phone number? Just as an example.