A structured format is really hard to stick to in a volunteer project environment, and creates more work than is necessary.

I feel there are only three things that could be done, which would make a huge difference:

Use the WP-Announcements emailing list & add a link to this in the README.
Tying announcements to WordPress itself is not practical as it relies on sites having a valid email address (not all do) and also relies on WP being able to access the install. Server permissions may make this impossible.
Release patches, not just full downloads.Where patches can be safely applied to different versions, say so.
Better commenting of code. If code is changed to harden security commenting it would enable users to identify where this hardening has taken place and fix their own code accordingly.

The ideas for improving alerts in the WordPress backend are good, but don't help those users who are running heavily customised installs, or who have locked their servers down so tight that they do not get upgrade notices, or see the dashboard feeds, or who manually apply fixes in a company-proscribed process.