Termos do cotidiano, especialmente quando usados para classificações, raramente admitem definições rigorosas como as que se usam nas ciências.
Por exemplo, é comum se falar em "pessoas e animais", apesar de pessoas, biologicamente, também serem animais. Nesse sentido, é importante deixar claro o contexto em que os termos estão sendo usados - aqui, o cotidiano/culinário, em oposição ao biológico/botânico.
O (curto) verbete da Wikipedia em português esclarece muito bem essa situação e vale a leitura (grifo meu):
Dentre as categorias de plantas alimentícias, ou comestíveis, os conceitos são bastante abrangentes e não excludentes.
Não são geralmente consideradas hortaliças as frutas, os frutos secos, as especiarias, os grãos, as batatas e algumas raízes tuberosas, como a mandioca. No entanto, do ponto de vista nutricional, todos estes produtos, com exceção das frutos doces, podem ser consideradas hortaliças.
Em botânica, os termos "fruto" e "legume" têm significados bem definidos, mas "hortaliça" e "verdura" não. Já em agronomia, em culinária e em linguagem popular, as definições podem variar, e o uso destes termos é muitas vezes indiscriminado. Alguns separam as plantas (ou suas partes) consumidas em frutas (vegetais doces) e hortaliças (vegetais não-doces) e, por sua vez, as hortaliças são divididas em verduras (consumidas cruas) e legumes (consumidos após cozimento). Outros separam as hortaliças com base no tipo de órgão: verduras seriam as folhas e flores comestíveis, e legumes seriam os frutos (no sentido botânico) não-doces, os caules e os órgãos subterrâneos (raízes, tubérculos e bulbos) comestíveis.
O termo legume, em botânica, serve para designar um tipo de fruto (no sentido botânico), também chamado vagem e as sementes que contêm, como os feijões.
Usualmente, as verduras incluem as folhas (por exemplo, da alface), caules (espargo) e raizes de diversas plantas, como a cenoura. Mas o termo pode também incluir frutos não-doces, como as vagens verdes (por exemplo, do feijão) ou as suas sementes (como as das favas), o pepino, os diferentes tipos de abóboras, tomates, abacates e pimentas.
Por extensão, consideram-se por vezes como hortaliças algumas sementes já maduras (secas), como as ervilhas e feijões, que se cozinham depois de ensopadas em água para facilitar a cozedura.
Diante dessa diversidade de conceitos, uma alternativa é o uso do termo generalista "planta comestível".
Update: Reiterando a busca sobre o assunto, encontram-se muitas fontes contraditórias na rede — provavelmente variações regionais e de contexto, além de interpretações pessoais. Há até quem afirme que frutas são uma categoria de legumes. Acho que fico com o encerramento de uma matéria da BBC Brasil a respeito:
Resumindo: vou continuar a ter as dúvidas que levantei no início deste post. Na boa: seria tudo mais fácil se fizéssemos que nem os ingleses, chamássemos todos eles de vegetais, e ponto.
