After spending quite some time on it, I have found the solution to your question.
It involves dealing with external calendars (Outlook, Facebook) on their respective websites.
First of all, on where the birthdays are stored: when you connect to Facebook on your phone, Outlook automatically imports all the birthdays into its calendar. You can view and edit them on the Outlook calendar website; there's a separate calendar there called Birthdays that you can change.
By default, you are subscribed to the Outlook/Hotmail birthday calendars. This is the setting you can change on the phone.
However, that is not all. Facebook birthdays are also stored in the Facebook calendar. As of today, there is no way to remove them from the Facebook calendar (Facebook doesn't allow that).
These birthdays won't show up on the phone, but you will still be notified about them (this made me search, in vain, for the topic "Windows phone notifies about deleted birthdays").
Nevertheless, Facebook allows one to subscribe/sync to its events and birthdays calendars separately (at least some sanity!), as per their help page. So the solution is to subscribe to Facebook events only calendar from another calendar of your choice (I created a new Outlook calendar), and have your phone display it. Turn off the Facebook calendar entirely on the phone, it is now duplicated on Outlook.
For the summary, I assume you are using the Outlook calendar.
- Turn off the Facebook calendar on the phone (... -> Settings -> Calendar(Facebook): off).
- Log in to Facebook desktop version. Go to events. Follow the instructions and obtain the subscription link for events (it's the link under "upcoming events" and starts with webcal://www.facebook.com/ical/u.php? ...)
- Log in to Live Calendar. If you prefer Live, hit Import, then Subscribe and enter the URL you got in Step 2. Call it "Facebook event sync" or anything you want.
- While you are there, edit the Birthdays calendar to your liking (delete birthdays you don't want, delete the calendar entirely, create a new one and put just the birthdays you want, etc).
- On your phone: open calendar, ... -> settings. Make sure the calendar you made in step 3 ("Facebook event sync (Hotmail)") is turned on. If you want to turn off birthday notifications entirely, turn off the Birthdays(Hotmail) calendar.
- If your phone has Battery Saver mode on, turn it off and wait for the calendar to sync (you may need to go to phone settings -> email+accounts -> Microsoft -> download new content -> as items arrive->OK to force sync).
Turn off Facebook calendar. Delete unwanted birthdays on Outlook, subscribe to Facebook events only from there.