I still say it sometimes, because, well, I'm not going to stop saying it altogether and sometimes it spontaneously just comes out of my mouth (and also... he says it too! So there! haha)
But, the bulk of the time with him, or even with friends, if they're telling me something that's frustrating, or that they're upset about, I'll simply listen. I'll make 'arg' noises, or shake my head, or do the body language/facial expression thing, but that's about it. I think just indicating - even if not in words - that you're listening to them and 'get' what they're expressing, can go a long way.
And, on the flip side... when I'm on the receiving side of hearing the 'I'm sorry', it's like.... as the receiver, you can't really respond to that. All you can do is acknowledge that you heard them say they're sorry, and shrug your shoulders or something. So, yeah, the words themselves don't 'do' a huge amount.