We've had similar problems. We've found the best solution is to have the tank with his back to the paladin, so that the tank is between the pally and Maiden. That way, Maiden has to clip through the tank to get to the paladin, giving more chances for consecrate to break the repentance.

We had issues with a layout like:

(M)(T)----(P) (Maiden, Tank with a gap to Paladin) because then as the Maiden moves to the Paladin she clips through the tank and gives him facing errors, we eventually went with a more side-on approach:

(M)
(T)---(P)

This puts Maiden a little closer to the paladin, but any reasonably-geared paladin (I run 7k completely unbuffed in pure healing gear) shouldn't be one-shot material even after the 2k repentance hit, you just need to keep yourself topped up - if you're dying quite a bit use Sac rank 1 instead of rank 4, the damage ticks of BoSac add up to quite a bit over time.

Also, I believe any hostile action, even refreshing demo/commanding shout, will turn Maiden back to you (with that, it's hard to understand why the warrior last night was having issues, maybe he was trying to sunder/slam her).

edit: to the best of my knowledge, Shade, the same Holy Ground tick that breaks the paladin out of Repentance also breaks the tank out of Repentance (since without damage on the tank the paladin wouldn't take damage), it's simply a matter of blizzard's combat logic deciding that the paladin broke 'first' (we're talking microseconds here) and Maiden switching aggro to the paladin (for some reason, ground ticks, it hits the tank, BoSac transfers some damage to the paladin, paladin takes damage, paladin breaks repentance, maiden switches aggro, then the tank breaks repentance after that).
In practical terms, as soon as the aggro switches to the paladin the tank should be able to get it back (excepting gcd issues) because they're breaking at the same time. All that putting the tank between Maiden and the paladin accomplishes is to make maiden have to take one more step to reach the paladin.