Edit:
Original answer follows here, for the actual queries used, look below at Update
Original answer
For anyone stumbling across the same (or similar) problem in the future. Here's what worked for me. After some more searching and trial and error, I've found following query to give me the results that I wanted:
SELECT caev.value FirstName, caev2.value LastName, caet.value Address, caev3.value City, caev5.value State, caev6.value Postcode, caev4.value Country, caev7.value Tel FROM customer_entity ce
JOIN customer_address_entity cae ON cae.parent_id = ce.entity_id
LEFT JOIN customer_address_entity_varchar caev ON caev.entity_id = cae.entity_id AND caev.attribute_id = 20
LEFT JOIN customer_address_entity_varchar caev2 ON caev2.entity_id = cae.entity_id AND caev2.attribute_id = 22
LEFT JOIN customer_address_entity_text caet ON caet.entity_id = cae.entity_id AND caet.attribute_id = 25
LEFT JOIN customer_address_entity_varchar caev3 ON caev3.entity_id = cae.entity_id AND caev3.attribute_id = 26
LEFT JOIN customer_address_entity_varchar caev4 ON caev4.entity_id = cae.entity_id AND caev4.attribute_id = 27
LEFT JOIN customer_address_entity_varchar caev5 ON caev5.entity_id = cae.entity_id AND caev7.attribute_id = 28
LEFT JOIN customer_address_entity_varchar caev6 ON caev6.entity_id = cae.entity_id AND caev5.attribute_id = 30
LEFT JOIN customer_address_entity_varchar caev7 ON caev7.entity_id = cae.entity_id AND caev6.attribute_id = 31
HAVING FirstName IS NULL OR LastName IS NULL OR Address = '' OR City IS NULL OR Postcode IS NULL OR Country IS NULL;
The attribute id's of required fields I got from following query:
SELECT * FROM `eav_attribute` WHERE `entity_type_id` = 2 AND `is_required` = 1 ORDER BY `attribute_id` ASC;
I've also added some non-required attributes to display a more detailed result for exporting to csv.
Update:
Here are the exacte queries I used to delete all customer addresses with empty required fields.
Query 1 to get all required fields:
SELECT * FROM eav_attribute WHERE entity_type_id = 2 AND is_required = 1;
(as provided by seeni)
This got me the following attribute_id's: 20 (firstname),22 (lastname),25 (street),26 (city),27 (country_id),28 (region),30 (postcode),31 (telephone)
Query 2 to get a list of all addresses which have empty required (just to get a visual representatation of all incomplete addresses):
SELECT ce.entity_id, cae.entity_id AdresId, caev.value Voornaam, caev2.value Achternaam, caet.value Adres, caev3.value Gemeente, caev5.value Provincie, caev6.value Postcode, caev4.value Land, caev7.value Tel FROM customer_entity ce
JOIN customer_address_entity cae ON cae.parent_id = ce.entity_id
LEFT JOIN customer_address_entity_varchar caev ON caev.entity_id = cae.entity_id AND caev.attribute_id = 20
LEFT JOIN customer_address_entity_varchar caev2 ON caev2.entity_id = cae.entity_id AND caev2.attribute_id = 22
LEFT JOIN customer_address_entity_text caet ON caet.entity_id = cae.entity_id AND caet.attribute_id = 25
LEFT JOIN customer_address_entity_varchar caev3 ON caev3.entity_id = cae.entity_id AND caev3.attribute_id = 26
LEFT JOIN customer_address_entity_varchar caev4 ON caev4.entity_id = cae.entity_id AND caev4.attribute_id = 27
LEFT JOIN customer_address_entity_varchar caev5 ON caev5.entity_id = cae.entity_id AND caev5.attribute_id = 28
LEFT JOIN customer_address_entity_varchar caev6 ON caev6.entity_id = cae.entity_id AND caev6.attribute_id = 30
LEFT JOIN customer_address_entity_varchar caev7 ON caev7.entity_id = cae.entity_id AND caev7.attribute_id = 31
HAVING Voornaam IS NULL
OR Voornaam = ''
OR Achternaam IS NULL
OR Achternaam = ''
OR Adres IS NULL
OR Adres = ''
OR Gemeente IS NULL
OR Gemeente = ''
OR Postcode IS NULL
OR Postcode = ''
OR Land IS NULL
OR Land = ''
OR Tel IS NULL
OR Tel = ''
Query 3 to delete all empty varchar entries:
DELETE FROM customer_address_entity_varchar WHERE entity_id IN (SELECT AdresId FROM (SELECT ce.entity_id, cae.entity_id AdresId, caev.value Voornaam, caev2.value Achternaam, caet.value Adres, caev3.value Gemeente, caev5.value Provincie, caev6.value Postcode, caev4.value Land, caev7.value Tel FROM customer_entity ce
JOIN customer_address_entity cae ON cae.parent_id = ce.entity_id
LEFT JOIN customer_address_entity_varchar caev ON caev.entity_id = cae.entity_id AND caev.attribute_id = 20
LEFT JOIN customer_address_entity_varchar caev2 ON caev2.entity_id = cae.entity_id AND caev2.attribute_id = 22
LEFT JOIN customer_address_entity_text caet ON caet.entity_id = cae.entity_id AND caet.attribute_id = 25
LEFT JOIN customer_address_entity_varchar caev3 ON caev3.entity_id = cae.entity_id AND caev3.attribute_id = 26
LEFT JOIN customer_address_entity_varchar caev4 ON caev4.entity_id = cae.entity_id AND caev4.attribute_id = 27
LEFT JOIN customer_address_entity_varchar caev5 ON caev5.entity_id = cae.entity_id AND caev5.attribute_id = 28
LEFT JOIN customer_address_entity_varchar caev6 ON caev6.entity_id = cae.entity_id AND caev6.attribute_id = 30
LEFT JOIN customer_address_entity_varchar caev7 ON caev7.entity_id = cae.entity_id AND caev7.attribute_id = 31
HAVING Voornaam IS NULL
OR Voornaam = ''
OR Achternaam IS NULL
OR Achternaam = ''
OR Adres IS NULL
OR Adres = ''
OR Gemeente IS NULL
OR Gemeente = ''
OR Postcode IS NULL
OR Postcode = ''
OR Land IS NULL
OR Land = ''
OR Tel IS NULL
OR Tel = '') AS AddressId) AND attribute_id IN (20,22,26,27,28,30,31);
Query 4 to delete all empty text fields
DELETE FROM customer_address_entity_text WHERE entity_id IN (SELECT AdresId FROM (SELECT ce.entity_id, cae.entity_id AdresId, caev.value Voornaam, caev2.value Achternaam, caet.value Adres, caev3.value Gemeente, caev5.value Provincie, caev6.value Postcode, caev4.value Land, caev7.value Tel FROM customer_entity ce
JOIN customer_address_entity cae ON cae.parent_id = ce.entity_id
LEFT JOIN customer_address_entity_varchar caev ON caev.entity_id = cae.entity_id AND caev.attribute_id = 20
LEFT JOIN customer_address_entity_varchar caev2 ON caev2.entity_id = cae.entity_id AND caev2.attribute_id = 22
LEFT JOIN customer_address_entity_text caet ON caet.entity_id = cae.entity_id AND caet.attribute_id = 25
LEFT JOIN customer_address_entity_varchar caev3 ON caev3.entity_id = cae.entity_id AND caev3.attribute_id = 26
LEFT JOIN customer_address_entity_varchar caev4 ON caev4.entity_id = cae.entity_id AND caev4.attribute_id = 27
LEFT JOIN customer_address_entity_varchar caev5 ON caev5.entity_id = cae.entity_id AND caev5.attribute_id = 28
LEFT JOIN customer_address_entity_varchar caev6 ON caev6.entity_id = cae.entity_id AND caev6.attribute_id = 30
LEFT JOIN customer_address_entity_varchar caev7 ON caev7.entity_id = cae.entity_id AND caev7.attribute_id = 31
HAVING Voornaam IS NULL
OR Voornaam = ''
OR Achternaam IS NULL
OR Achternaam = ''
OR Adres IS NULL
OR Adres = ''
OR Gemeente IS NULL
OR Gemeente = ''
OR Postcode IS NULL
OR Postcode = ''
OR Land IS NULL
OR Land = ''
OR Tel IS NULL
OR Tel = '') AS AddressId) AND attribute_id IN (25);
Query 5 to delete the affected address entities:
DELETE FROM customer_address_entity WHERE entity_id IN (SELECT AdresId FROM (SELECT ce.entity_id, cae.entity_id AdresId, caev.value Voornaam, caev2.value Achternaam, caet.value Adres, caev3.value Gemeente, caev5.value Provincie, caev6.value Postcode, caev4.value Land, caev7.value Tel FROM customer_entity ce
JOIN customer_address_entity cae ON cae.parent_id = ce.entity_id
LEFT JOIN customer_address_entity_varchar caev ON caev.entity_id = cae.entity_id AND caev.attribute_id = 20
LEFT JOIN customer_address_entity_varchar caev2 ON caev2.entity_id = cae.entity_id AND caev2.attribute_id = 22
LEFT JOIN customer_address_entity_text caet ON caet.entity_id = cae.entity_id AND caet.attribute_id = 25
LEFT JOIN customer_address_entity_varchar caev3 ON caev3.entity_id = cae.entity_id AND caev3.attribute_id = 26
LEFT JOIN customer_address_entity_varchar caev4 ON caev4.entity_id = cae.entity_id AND caev4.attribute_id = 27
LEFT JOIN customer_address_entity_varchar caev5 ON caev5.entity_id = cae.entity_id AND caev5.attribute_id = 28
LEFT JOIN customer_address_entity_varchar caev6 ON caev6.entity_id = cae.entity_id AND caev6.attribute_id = 30
LEFT JOIN customer_address_entity_varchar caev7 ON caev7.entity_id = cae.entity_id AND caev7.attribute_id = 31
HAVING Voornaam IS NULL
OR Voornaam = ''
OR Achternaam IS NULL
OR Achternaam = ''
OR Adres IS NULL
OR Adres = ''
OR Gemeente IS NULL
OR Gemeente = ''
OR Postcode IS NULL
OR Postcode = ''
OR Land IS NULL
OR Land = ''
OR Tel IS NULL
OR Tel = '') AS AddressId)
Hopefully this will be helpfull to some in the future, as it took me quite a lot of trail and error to get this right.