(1) It is a shame his feedback says otherwise. = It (his feedback says otherwise) is a shame.
(2) It is a shame THAT his feedback says otherwise. = It (THAT his feedback says otherwise) is a shame.
(a) It is more formal to introduce the noun clause with THAT.
(3) If you decide to write a sentence without "it," then you MUST use "that":
That his feedback say