Quitting the Notes app and restarting it doesn't help. The power switch on the phone has broken, so I can't try rebooting the phone.
Conclusion I got the power switch repaired (at the shop at the Milton Road / Arbury Road junction); disabling and then re-enabling synchronisation with iCloud made the notes come back. My contacts had also vanished, but again disabling and re-enabling synchronisation brought them back.
I suspect 11 May 2012 is relevant because it'll have been the day I updated the phone to iOS 5.1.2