This is a weird one. I bricked my current iPhone with a quick spin through the washing machine, so I dug out my old iPhone 4 to use in the interim before I get a replacement.
I deleted all the content and set it up as a new phone, and linked my iCloud account to it. It brought in all my notes, but they're old versions, including some notes that have been deleted.
My iPad, MBP and iMac are all syncing perfectly.
I turned off iCloud notes in settings and back on again, but the same (old) notes came back in again.
I created new notes on all devices:
"Note on iPhone"
"Note on iCloud.com"
"Note on MBP"
"Note on iMac"
"Note on iPad"
All devices but the iPhone synced with each other. The "Note on iPhone" didn't populate to anywhere else.
I am 100% convinced that I am using the correct Apple ID.
I decided to try using my husband's Apple ID, too. The exact same thing happened. The iPhone got old versions of his notes - eg, a particular note is dated Sept '15 on in phone, but May '16 on icloud.com and on his phone.
I checked that the date and time are set correctly.
Any other ideas?