Re: Batman vs. Deadpool -- eh. It's not like Batman fights to kill, so being unkillable doesn't really help Deadpool in that fight. If you throw that out the window, it's basically Batman vs. a psychotic guy with an arsenal. In other words, Batman's bread and butter.
*Geek mode engaged*
A psychotic guy with an arsenal who in between bouts of madness and breaking the fourth wall also happens to be one of the best assassins/bounty hunters/general badasses in the Marvel Universe... at least on the level of Slade in the DCU, and Slade's managed to beat Batman 1 on 1 when Batman *had* preparation time. Outside of his occasional contests with Deathstroke, the closest Batman comes to facing someone like Deadpool on a semi-regular basis is probably Bane... and while Deadpool lacks Bane's intellect or physical strength he does have more guns. A lot more guns. And bombs. And bazookas. And swords. And did I mention guns?
Obviously each writer handles how powerful/talented a character is differently (see both Superman and Wolverine for guys who regularly leap up and down the power charts) and with the whole "Crazy Bat God" thing, Bruce can be written to be virtually unbeatable. The version of Bruce I like isn't that though. He's the one who is arguably worse in a fight 1 on 1 then Nightwing even with prep time but succeeds because he applies his detective and strategic skills around it. I think the Batman of Rock of Ages is my personal canon (albeit it's a non-canon story); no crazy bat god, no ridiculous foresight, just an intelligent, sensible and excellent plan that allows Batman to punch well above his weight with the help of his allies, although at a great cost.