Were it me, I would timestamp every note rather than making it optional. People are always writing stuff down and forgetting where the note is, but I bet you they can remember the ball-park of when they wrote it. So, you're giving them a comon place to put all of their notes, but it sounds like the organization scheme is completely optional. Timestamping each note at least gives them an organization that they are familiar with and can use in lieu of creating their own.

Serialised data structures (either with Data::Dumper or YAML): easy to 'parse', but relies too heavily on storing all items in memory.

Who says you need to store all of the items in memory? Who even says that you even need the entire contents of a single record in memory?