Oikea lokero löytyi lopulta, mutta paketin hakeminen pakettiautomaatista kesti pitkään.

Because the verb here is löytyä, not löytää.

• löytää = to find something
  
  • Löysin oikean lokeron. = I found the right compartment.
• löytyä = to be found / turn up / be located

With löytyä, the thing that is found is the subject of the sentence, so it stays in the nominative:

• Oikea lokero löytyi. = The right compartment was found / turned up.

So even though English may express this with an object, Finnish structures it differently.

Not exactly. Löytyi is not the Finnish passive here. It is the past tense, 3rd person singular of löytyä.

So:

• löytyi = was found / turned up / was located / showed up

It often feels passive in English, but grammatically in Finnish it is an ordinary verb form, not the passive.

That is why oikea lokero is the subject:

• Oikea lokero löytyi lopulta.

A natural English idea is:

• The right compartment was eventually found
• or The right compartment finally turned up

Lopulta means finally, eventually, or in the end.

In this sentence:

• Oikea lokero löytyi lopulta
  = The right compartment was found eventually

It is an adverb, and Finnish word order is flexible, so you could move it for emphasis:

• Lopulta oikea lokero löytyi.
• Oikea lokero löytyi lopulta.

Both are fine, but the version in your sentence sounds neutral and natural.

It is a -minen noun formed from the verb hakea.

• hakea = to fetch / to pick up / to collect
• hakeminen = fetching / picking up / collecting

So:

• paketin hakeminen = collecting the package / the collecting of the package

This is very similar to an English -ing form used as a noun:

• Reading the book was fun.
• Kirjan lukeminen oli hauskaa.

In your sentence, the whole phrase paketin hakeminen pakettiautomaatista is the subject of kesti:

• paketin hakeminen pakettiautomaatista kesti pitkään
• collecting the package from the parcel locker took a long time

Because the -minen form behaves like a noun, and its object is commonly put before it in the genitive.

So:

• paketin hakeminen = the collecting of the package
• kirjan lukeminen = the reading of the book
• auton korjaaminen = the repairing of the car

Compare the finite verb version:

• Haen paketin. = I’ll pick up the package.

With hakeminen, the action is turned into a noun, and the object becomes a kind of dependent of that noun, so paketin is natural here.

Because -sta / -stä is the elative case, which often means out of or from.

• pakettiautomaatti = parcel locker / parcel machine
• pakettiautomaatista = from the parcel locker

The package is being collected from that place, so the elative is used.

You can think of it like this:

• automaatista = out of/from the machine
• kaapista = out of/from the cupboard
• laatikosta = out of/from the box

So pakettiautomaatista is very natural here.

Kesti is the past tense of kestää, which means to last or to take.

So:

• kesti pitkään = took a long time / lasted a long time

Pitkään is the normal adverbial form here meaning for a long time.

Common patterns:

• Se kesti pitkään. = It took a long time.
• Odotin pitkään. = I waited a long time.

A learner may expect something like pitkästi, but that is not the normal choice here. Pitkään is the idiomatic form.

Also compare:

• kauan = a long time
• kesti kauan = also possible

But kesti pitkään sounds very natural.

The second clause is:

• mutta paketin hakeminen pakettiautomaatista kesti pitkään

Its structure is:

• mutta = but
• paketin hakeminen pakettiautomaatista = collecting the package from the parcel locker
• kesti = took / lasted
• pitkään = a long time

So the whole sentence has two main clauses joined by mutta:

1. Oikea lokero löytyi lopulta
2. mutta paketin hakeminen pakettiautomaatista kesti pitkään

This is a very natural Finnish sentence structure.

Yes, two things in particular:

1. löytyä is very Finnish
   Finnish often uses löytyä where English might prefer find or a passive expression.
   So Oikea lokero löytyi lopulta sounds natural and idiomatic.

2. -minen for actions as nouns is extremely common
   paketin hakeminen is a standard way to say collecting the package.

So this sentence is a good example of very ordinary, natural Finnish:

• first clause with löytyä
• second clause with a -minen noun phrase as subject