Perhaps the datasheet view was in readonly mode?
It wasn't read-only because I could edit all records, delete was working fine when selecting the record and using the DEL key and also when you open a database in read-only mode you usually get a warning. After a quick chat with office support they confirmed it was a bug (with no patches in sight) and that the easiest workaround was disabling layout view. It's really strange that they still didn't notice and fix this bug earlier, considering that most access demo projects make heavy use of those datasheet views. What a disappointment!