If you love them, keep them! I had a similar experience with the So Private in blush/gold. I called the Saks website to get them to locate a pair for me in a store since they were sold out online. There were two pairs in the entire U.S., according to the store locator. One was in Houston. It was a size 37. Now, I usually wear a 36 or 36.5 in CL's, so I thought it was a long shot that the 37 would fit, but I liked them so much I told myself I'd try them and if they didn't fit, I'd just take them back to my Saks here. I tried them on, and voila! It was love.
Honestly, I have some extra room in the back, BUT I don't think it looks bad at all. In fact, I hate it when your heel hangs off in a slingback -- I would rather have extra room than not enough, or have my heel exactly meet the edge. I've worn them a couple of times, and I haven't had any issues with the straps. Also, I think an insole would help a lot, like some of the others have suggested. I think they are really pretty on you -- nice legs!