What version of Notes are you using? My wife had similar sync issues when her company was on Notes 6 or 6.5. Her issues cleared up when they moved her to 7 I think it was. Her company (16,000+ NA users) switched to Lookout and Exchange. Sync with their Blackberries and Palmie devices was one of the reasons why.
I've only used Notes once in my life and that was enough to convince me never to use it again so I am afraid the only help I can provide is that it might be your version of Notes.