I have removed all the permission sets from an account, but the permission set icon is still displayed. Why is that?

This is because the icon is displayed for all accounts that can use permission sets. It does not indicate whether an account has any permission sets allocated to it.