Hi Andrew,
I've not been in Mallorca as late as xmas but have been there in mid-October> late October (2 years ago). At that time I bumped into a retired guy at the "sewage works" near Alcudia who spends his winters in Mallorca & I can recollect his comments regarding winter birding there.
Expect black-necked & little grebes @ Albufera & Albufereta. Balearic & Cory's shearwater will have dispersed but apparently some return early & so it would be worth checking the point at Formentor. The distinctive Med. race of Shag should be about as will wintering Cormorant.Of the herons Grey, Little Egret & Cattle Egret will be around as should 1 or 2 Great-whites (I've seen them in October & April at the Albufereta) & apparently a few winter at the Albufera. There is at least one resident Sacred Ibis at the Albufera (it roosts in the heronry at the park entrance) & Glossy Ibis in winter are occasional( but then again they are in Devon too!). Apparently Bittern winter but Little bittern will have gone though the odd Night heron might linger.Expect Red-crested Pochard, Pintail, Teal, Shoveler,Tufted duck,Pochard,Mallard; possibly Ferruginous duck & if you're lucky Marbled teal & the odd White-headed duck are possible.
Raptors: Black(Cinereous) vulture is easy to see-perhaps more so at this time of year-try Lluc monastery or the Bocquer valley.Red kite is getting rarer on the island however. The Mallorcan Ospreys seem to be resident as are Marsh harrier & Peregrine. Apparently the odd Booted eagle may overwinter as do the Egyptian vultures on Menorca. I believe a pair of the E. vultures have moved onto Mallorca & so these might be a possibility in the Bocquer valley. Sadly Eleonora's falcon will have gone-they are almost common in October & apparently some young birds linger but probably not into December.
Purple gallinule should be easy @ Albufera. Interesting waders are likely with the Salinas on the southwest of the island likely to have Avocets, Little stint,Kentish plover,Common & Green sands (also Flamingo) while the salinas near Alcudia can also hold good waders. Stone Curlew are resident but sparse. Yellow-legged & Audoin's gull are also likely(probably guaranteed!).Kingfisher is apparently also quite common in winter, whilst apparently the Mallorcan Hoopoes are primarily resident. ***Wryneck is resident***(as ssp. mauritanicus-check out the orchard below the Bocquer Finca).
Passerines of interest: Thekla lark, Grey wagtail,White wagtail; Crag martin ( a few late/early Swallows are also possible), possible wintering Water pipit, Black redstart; apparently a few Bluethroat winter at the Albufera, whilst Alpine accentor is a scarce but regular visitor. Stonechat & Blue rock thrush are resident (Bocquer valley). Resident warblers include: Sardinian, Blackcap,Cetti's,Zitting cisticola,Moustached(a must-see at Albufera!),Marmora's (another wee sweetie!) & possibly Dartford's ( Ca'n Picafort coastal scrub & perhaps Arta). Firecrest, Serin & Crossbill in conifer woodland-try the forrest near the Formentor hotel, Raven in the mountains (Lluc, Bocquer valley, & did I mention Red-legged partridge?), Corn & Cirl bunting (around the Bocquer Finca).
All in all a list of in excess of 80 birds should be quite feasible & since the island is poorly birded over winter the odd wee surprise is also likely (previous winter records of Citril & Snowfinch!)
You would need to get accomodation in Puerto Pollensa or Alcudia to access the best sites. Since there's no point in thrashing the migration hotspots I suspect you would be better in Alcudia to allow early morning visits to the Albufera as this is probably the best single site & you would need a hire-car for Formentor, Cuber, Calle Bocquer ,etc.
Alternatively get a cheap flight to Malaga, hire a car & drive to El Rocio; stay in the excellent but well-priced El Toruno hotel with your balcony overlooking the "mother of marshes" & have the european winter birding holiday of a lifetime in one of the warmest parts of Europe at this time of year. If you have a non-birding spouse then there's lots to see & do (no, I'm not on commision!).
Happy holidays,
Steve