Where should I be storing custom node-related data?
I would suggest making your own table in the database, it's a perfectly acceptable practice if you name the table something unique that isn't likely to collide with other modules.

The database API is an extremely useful resource for this.



[edit:] Thanks to J. Reynolds - in this instance you will definitely need to tell Views about your table.