I think the comment that was in their communication that "if the relevant papers from the journal are not cited, they might consider the work to be out of scope" should apply to major relevant papers in that topic (whether it is in that journal or not) should be mentioned. It should not particularly be from THAT journal, I would have thought.
I can only say that in terms of my own experience, I have written articles without references from that journal and those were accepted (thankfully).
Rejecting a manuscript solely due to non-citation or referencing the editor's journal seem unethical to say the least. Such clauses as above suggest that the editor is craving for citations to probably improve the Impact Factor of his journal. Anyway, the good thing is that the same paper is under consideration for acceptance in another similar, if not better, journal. Thanks.