I only noticed this thread last night (and was preoccupied then by something else).
Doing the Cape Verdes comprehensively should be a lot easier than it appears to be. Regular tourist holidays go to Boa Vista these days from English airports and there are regular (daily?) flights between Boa Vista (Rabil) and Santiago (Praia). However, internal flights have the reputation of being chaos and one more island is needed than those two!
My sightings on a bird tour - April/May 2013:-
Boa Vista - White-faced Storm-petrel, Madeiran Storm-petrel, Red-billed Tropicbird, Brown Booby, Magnificent Frigatebird, Alexander's Kestrel, Black-crowned Sparrow-lark, Bar-tailed Desert-lark, Greater Hoopoe-lark, Brown-necked Raven & Iago Sparrow. In a Western Paleartic context you need to visit for Magnificent Frigatebird and you can see the storm-petrels at a colony. They are seen from tourist whale-watching boats I believe as well. I only saw Iago Sparrow but I believe the Swift occurs.
Santiago - Fea's Petrel, Cape Verde Shearwater, Boyd's Shearwater, Red-billed Tropicbird, Brown Booby, Black Heron, Western Reef Heron, Intermediate Egret, Bourne's Heron, Cape Verde Buzzard, Alexander's Kestrel, Helmeted Guineafowl, Cape Verde Barn Owl, Cape Verde Swift, Grey-headed Kingfisher, Black-crowned Sparrow-lark, Bar-tailed Desert-lark, Greater Hoopoe-lark, Cape Verde Cane-warbler, Brown-necked Raven & Iago Sparrow. All of the endemics occur here save for Raso Lark (and possibly if you take a 'proactive' approach to taxonomy the Peregrine which is the toughest to see).
This solely leaves Raso Lark which effectively sits on an island between Sao Nicolau (Neglected Kestrel and Cape Verde Peregrine seen) and Sao Vicente.
I would have thought the cheapest approach is to go for a fortnight's package holiday on Boa Vista and try to get to Santiago for a couple of days in that fortnight. We did Santiago for two days. However, the missing species would require more effort. Our experience of getting to and from Sao Nicolau was the most chaotic. Once there you have access to fishermen, boat trips and (even more) seawatching.
Visas were available on arrival when I went.
It is a well-trodden path:-
http://www.surfbirds.com/trip_report.php?id=795
All the best