Tottenham showed no hangover from their Carling Cup Final defeat against Manchester United last Sunday and eased their relegation worries as they moved clear of the bottom three.
Lennon was the difference between the two teams and capped his night with two superb goals as he looks to force his way back into the England squad.
Keane also had a night to remember as he scored his first goal since rejoining the club from Liverpool during the January transfer window to make it back-to-back wins for Redknapp's side in the Premier League.
Despite beating Liverpool last weekend, Middlesbrough boss Gareth Southgate must have major worries over his side's attempts to stay in the top-flight as they crashed to their seventh away defeat on the spin.
It could have been a different story if Middlesbrough had broken the deadlock after just two minutes.
Jonathan Woodgate, who missed out on the Carling Cup Final through injury, made a big mistake which allowed Stewart Downing the chance to fire a low shot from the edge of the box which produced a fine save from Heurelho Gomes diving low to his left.
Boro were made to pay as Tottenham opened the scoring on nine minutes.
Luka Modric's corner was flicked on by Michael Dawson and Keane was in the right place to strike the ball home from close range to make it a dream start for the home side.
Southgate must have known it was not going to be his night when Sanli Tuncay saw his superb effort ruled out on 11 minutes.
Downing played a high ball over the top of the Tottenham defence. Tuncay reacted the quickest and struck a blistering shot past Gomes into the back of the net, but his effort was ruled out for offside.
Tottenham raced down the other end and grabbed their second of the game on 14 minutes.
Modric produced a great piece of skill to take the ball past Robert Huth and played the perfect pass into Roman Pavlyuchenko, who slid the ball past keeper Brad Jones to put Tottenham in pole position.
Modric was involved in the heart of the action once again on 34 minutes when he released Keane into the penalty box and he saw his shot well saved by Jones who raced out of his goal.
Tottenham gave the home fans even more to shout about when Lennon added a third on 40 minutes.
Keane turned provider and played the perfect pass into Lennon, who was totally unmarked and he kept all his composure to strike the ball past Jones.
Boro could have grabbed a lifeline on the stroke of half-time. Gary O'Neil's cross fell to Jeremie Aliadiere who was totally unmarked, but he flashed his header wide of the post.
Boro then hit the woodwork on 65 minutes when Tuncay's lob over Gomes came back off the post.
But it was left Lennon - the star man on show - to grab his second of his game and Tottenham's fourth on 79 minutes.
Keane flicked the ball into the England winger and he lobbed his effort over Jones into the back of the net to make it an even longer journey back to the north east for Southgate's side.