No.
An Roínn Oideachais is correct. Oideachas is a genericised noun here, just like in an sagart paróiste.

Fianna Éireann: both nouns are definite, and no article is required.

Éireann vs na hÉireann: Éireann is used for more "quintessentially" Irish things, rather than incidental qualities. However, this principle is only partly applied, and you have to look at word collocations too. Fir Éireann has no article in the middle. Muíntir na hÉireann does. And those are the correct idiomatic forms.

An bhean tí: this is correct. It subtly contrasts with bean an tí.

Hmm. So are you saying that 'Roinn an Oideachais' is outright grammatically incorrect? Or is it that there is a difference in meaning between 'Roinn an Oideachais' and 'An Roinn Oideachais'?
--
On the other hand, I get your distinction between 'an sagart paróiste' and 'sagart an pharóiste', and equivalently between 'an bhean tí' and 'bean an tí'. This distinction can be seen as one of generic versus specific uses of the noun that's in the genitive.

Generic Sense:
In the phrase 'bean tí' (literally 'a woman of house'), the word 'tí' is being used in a generic sense. So rather than there being any specific house in mind, it's effectively referring to the general concept of 'house'. In this way, 'tí' is acting essentially like an adjective. And, like adjectives can, 'tí' here serves to categorise the word 'bean' i.e. put the word 'bean' into a specific category that might be distinct from other categories of women e.g. women who are lodgers, etc.
Once the indefinite phrase 'bean tí' is introduced in text or conversation, it is typically preceded by the definite article from then on i.e. it is henceforth a definite noun. e.g. 'Do bhíos ag labhairt le bean tí inné. 'Sé a dúirt an bhean tí seo liom ná...'

Specific Sense:
On the other hand, with the phrase 'bean an tí' (literally 'the woman of the house'), there is a specific house in mind. So, typically the house in question will already have been introduced in the text or conversation, e.g. 'Do bhuaileas isteach i dtigh inné. D'ofráil bean an tí cupán tae dhom.'

-
I think the distinction is more obvious in the plural: mná tí (women of house) versus mná an tí (the women of the house).
The phrase 'mná an tí' implies that the women are all associated with a single house, whereas there is no such implication with 'mná tí'.
The phrases 'an sagart paróiste' and 'sagart an pharóiste' can be analysed in the same way.

However, I am struggling with the names of government departments. For some reason, my mind doesn't want to accept constructs like 'An Roinn Oideachais' at an instinctive level, although I'm struggling to articulate why. But please indulge my - possibly flawed - logic below.

Imagine a situation where there are several government departments dedicated to education (each to a certain aspect of education, let's say), and possibly likewise several for health, etc.

So you might say: 'Tá ceithre roinn oideachais in Éirinn ach is í an roinn oideachais is tábhachtaí ná Roinn na mBunscol. Tá níos lú tábhachta ag baint leis na ranna oideachais eile'.

And you might say: 'Is roinn oideachais í Roinn na mBunscol. Tá tábhacht ar leith ag baint leis an roinn oideachais seo.'

The word 'oideachais' is used above for the purpose of categorising. E.g. Roinn na mBunscol belongs to a category of departments known as 'na ranna oideachais'. A specific member of this category would typically be referred to as 'roinn oideachais' upon first being introduced, and as 'an roinn oideachais' thereafter.

On the other hand, imagine if there was only one department devoted to education. In this case, there is no category of department called 'ranna oideachais' since a category or set typically involves more than one member. So, you might say something like: 'In Éirinn, tá roinn amháin dírithe ar an oideachas, agus is é an t-ainm atá ar an roinn seo ná 'Roinn an Oideachais'.

I'm not saying I'm right here but since, in the last example above, there is no intention to categorise i.e. indicate membership of a category, that's why, in my mind, it makes more sense to say 'Roinn an Oideachais' than 'An Roinn Oideachais'. (That's also why I used 'Roinn na mBunscol' in the first example above, rather than 'An Roinn Bunscol'.)

To summarise (according to my - possibly flawed - logic):
'Roinn an Oideachais' - 'The (one and only) department devoted to education'
'An roinn oideachais' - 'The department currently under discussion, being one of the departments in the 'education' category.'

Of possible significance also is that the names of government departments make use of abstract nouns e.g. 'oideachas', 'airgeadas', 'sláinte'. Being abstact nouns, they are also non-countable i.e. they have no plural (at least in their typical senses).

Non-countable abstract nouns can be seen as being definite nouns, at least from a semantic point of view. e.g. 'Education is of key national importance.' The word 'Education' here is essentially encompassing all the education in the world and so can be seen as definite.

(Although there can be indefinite senses to abstract nouns too e.g. 'He obtained an education in languages.)

Now, as far as I can see, in Irish (and unlike English), non-countable abstract nouns are typically preceded by the definite article. For example, contrast the words 'sláinte' and 'health' in the following: 'Is fearr an tsláinte ná na táinte' versus 'Health is better than wealth'.

So you could build up a phrase as follows:
English -> Irish
Education -> An Oideachas
The Department of Education -> Roinn an Oideachais

Consider on the other hand the Irish mythical tale 'An Bradán Feasa', a title which contains the genitive of the abstract noun 'fios' (knowledge). The story concerns a salmon upon whose eating the eater will be granted special knowledge or wisdom. As far as I know, the eponymous salmon was one of a kind i.e. it wasn't a member of a set of such salmon. Yet the story is commonly referred to as 'An Bradán Feasa', and not 'Bradán an Fheasa'. This would tend to validate the use of expressions like 'An Roinn Oideachais' instead of 'Roinn an Oideachais'.

And indeed, an internet search of 'An Bradán Feasa' yields multiple results, although practically all are English language websites.

On the other hand, a search for 'Bradán an Fheasa' yields only one result, although it's an Irish language website.

-
It occurs to me also to search for 'Roinn an Oideachais'. I've got several results, including from websites that seem very professional. See examples below.

https://colaisteide.com/
https://assets.gov.ie/25310/68cf8ab4f10 ... 9c3f03.pdf
https://www.uni-due.de/DI/DI_Official_Status.htm

This leads me to believe that there is validity in grammatical constructs of the style 'Roinn an Oideachais', where the modifying noun (the one in the genitive) is an abstract noun.

Roínn - this word has a long vowel in Cork. It is pronounced Reeng
Oideachas - this word has the stress on the first a in the word in Cork. It is pronounced idyAchas
By the way, this word is masculine, and so would be an tOideachas, with t-prefixation.

Roínn an Oideachais would mean THE department of THE education.
An Roínn Oideachais would mean The department of education.

It comes down to the issue of whether an abstract noun such as oideachas should have the article or not. I discussed this a bit in my article on the article (you can get this from me at foghlamthoir@gmail.com)

Roínn an mBun-scoil - this is OK as it is the department that deals with the primary schools.

A good example is bás, an abstract noun. Fuair sé bás. You don't say "fuair sé *an bás". In uacht bháis (at death's door). Not in uacht an bháis. I think abstract nouns take the article when there is an attempt to discuss the abstract concept as a whole in some way, but it is a understudied aspect of Irish grammar.

Interesting. Actually I think you sent that on to me already. I must get around to reading it.