Yeah, I know, this topic has been covered before.
1) I have checked the trash, it's empty
2) I have changed the permalink structure from one to another and then back
3) I have created a custom structure of /english/%postname%/ and it didn't work.
W T F