I found the solution and instead of deleting the question, I am writing my answer to help someone else who may face the same issue.
In order to remove specific interactions from a regression, I converted all categorical variables into dummy variables. We now have a variable associated with each category whose interaction can be easily excluded from the model specification (The reference categories must also be excluded, obviously).
I excluded the problematic interaction from the formula and it worked without any rank deficient error either with or without random-effect.
