“If I offended you with my comments, I apologize”
“My apologies if you took it the wrong way. It’s my fault for overestimating my audience”
“I agree it was insensitive for me to say that. If what I said was wrong, I’m very sorry.”
“I’m sorry I made that remark. In the future, I will keep in mind how sensitive some people can be.”
“I’m sorry for being so testy. It’s a character flaw that I don’t suffer fools gladly.”
Need more!
I’m sorry you feel that way.
I’m sorry that you misunderstood me.
Reminds me of Seinfeld (what doesn’t, and this very episode came up in another thread just today!):
HANKE: All right, George, all right. I’m sorry. I’m very, very sorry. I’m so sorry that I didn’t want your rather bulbous head struggling to find its way through the normal-size neck hole of my finely knit sweater.
…
HANKE: Well, I talked to my sponsor, and, uh, I’ve thought it over, and, you know, my apology at the coffee shop was sarcastic, and rude, and you deserve much better.
GEORGE: (ready to leave) Well, thank you.
HANKE: You’re welcome.
I’m sorry; I know some people are easily confused.
I’m sorry that you have a problem with it.
Oh, I’m very sorry you had to hear that; in the future I’ll only say such things when you’re not around.
I’m sorry; I didn’t mean to make you look bad.
Oh, you couldn’t find it? That’s fine, it’s right here. You just must not be that good looking.
You know these days I have no idea what sort of apology is acceptable to all the “that’s not good enough” offenderatis. All I can say is “sorry,” but apparently that’s just never enough.
I’m increasingly leaning towards “fuck you. I’m not as sorry as you demand and I never will be. Hate me if it makes you feel better.”
I’m sorry you’re all not more like me.
I’m sorry you’re such a bitch.
the problem is that you almost never hear an apology that just says “I did something wrong, and I’m sorry.” It always uses the weasely versions in the OP, that really say “I didn’t do anything wrong, but it’s a pity that people got all bent out of shape about something.”
I’m very sorry that you feel that is a problem. 
I’m sorry you’re sufficiently easily offended to require me to submit this apology. Fuck off.
I’m sorry, I forgot you were just a woman.
I’m sorry if my beliefs bother you; I can’t help it if I’m right.
Look, I’m sorry, but it’s not like I was actually trying to win.
I’m sorry you didn’t understand; sometimes I have trouble simplifying things enough for you.
Look, I’m sorry; i’t’s not like I’d do this if I had a choice, but the Bible clearly demands that you be killed. You have no idea how bad that makes me feel.
I’m sorry, I forgot whom I was dealing with.
“What’s a beautiful girl like you doing on the end of my nob? Oops, sorry, wishful thinking.” -Adrian Edmondson
I show up for a blind date
Me: Hi!
Him:… Sorry, dude, this just isn’t going to work.
:smack: 
From Chicago (the bit with Lucy Liu):
“Are you sorry, dear?”
“Sure, I’m sorry. Sorry I got caught!”
What, you’d’ve preferred:
You: Hi!
Him: Aiiii!!! :: runs screaming from the premises ::
Let me preemptively apologize and say I’m sorry if you found that offensive.
Welll So-Reee!
Well, it would have at least been nice if he had stayed for coffee after dragging me across town. 
Having seen your picture (somewhere here on the boards) and read quite a few of your messages I can safely say I would neither run screaming or decline a date.
In the spirit of the thread, I’m sorry that you were offended by his actions.