We would like to express our sincere apologies for any inconvenience caused.

Vielen Dank, das klingt natürlich sehr gut.

Dennoch:
Sind die beiden von mir angeführten Sätze ebenfalls möglich und richtig und was ist der Unterschied zwischen beiden?

sincere/sincerely is good.

"Deeply" is also OK in this grammatical context, but it expresses a much more profound apology. Think of a Japanese company president whose food products have made people sick. It's not likely that your situation requires this.

"for the inconvenience" admits that there was inconvenience. "for any inconvenience" says: if there was any inconvenience, we apologize for it (but maybe there wasn't). But practically speaking, both work. No one will think carefully about the meaning. They'll just understand that you're apologizing. "Sincerely" is just an intensifier.

"We would like to apologize sincerely ..." is about the same as "we would like to sincerely apologize". Some people don't like a split infinitive (to sincerely apologize), simply due the grammar. But a split infinitive is quite common, and generally accepted.

P.S. apologize is the American spelling, apologise is British.

Thank you very much for your very helpful reply!

(Now that you mention it, I remember that Microsoft Word's grammar correction always warns about split infinitives.)