I had the same issue with my UD40. The pad is much too large and doesn't slide, so I can't easily move the bag from one shoulder to cross-shoulder carry, etc.
My solution was to get the shoulder strap that came with my Think Tank Speed Demon waist pack. It's narrow but padded, and has a sliding non-slip wrapper. MUCH better. You might contact TTP and see if they'll sell you one.
As for your other suggestions, the Retrospective strap is nice, but not removable. I use the Upstraps for my cameras, and I thought about the Upstrap for shoulder bags, but didn't get that far.