Dad's Deli is the name of the restaurant/home where Rusty and his parents live.
At one point, Rusty's parents opened a restaurant shop in their home in Beige Town. As Rusty's dad told him to deliver the Chicken Panini to Professor Tree, Rusty instead runs away from home and left the Chicken Panini undelivered.
After Rusty steals his Dad's credit cards to buy a bike, the shop was most likely to be bankrupt and closed down. In the timeline altered by Future Rusty, The restaurant was never remained closed down due to Past Rusty remains to work as a Deli boy.
After the damage was undone by Peanut Butter, Future Rusty took his Past counterpart's place (due to travelling with Peanut Butter & Cleffaye) with Pikachu as an additional worker.