Yes, they really added you back, unless the friends you have been chatting with used bots, in which case the process of adding you back is automatic. When unblocked, the request appears in the client. Also, requests, messages, stories, etc., are stored encrypted on the server for 30 days. It's possible they have been there for a long time, and that's why you received notifications.