Repeated Squaring
If Euler wasn't mentioned I would consider it a problem about repeated squaring:
$$
\begin{align}
7^2&\equiv 49\\
7^4&\equiv 49^2\equiv 1\\
7^8&\equiv 1^2\equiv 1\\
7^{(2^n)}&\equiv 1\mbox{ for }n>1
\end{align}
$$
Now $355=101100011_2=2^8+2^6+2^5+2^1+2^0$ and so accordingly
$$
\large
\begin{align}
7^{355}&=7^{2^8+2^6+2^5+2^1+2^0}\\
&\equiv7^{2^1+2^0}\\
&=343\\
&\equiv 43
\end{align}
$$
Chinese Remainder Approach
Knowing the Chinese Remainder Theorem then simplifies the size of the calculations since modulo 25 we have $7^2\equiv -1$ and $7^{4k}\equiv 1$ and therefore $7^{355}\equiv 7^3\equiv -7$ modulo 25.
At the same time we have $7^2\equiv 1$ modulo 4 so that $7^{355}\equiv 7\equiv 3$ modulo 4. Now $25\equiv 1$ modulo 4 and $-24\equiv 1$ modulo 25 so
$$
7^{355}\equiv 3\cdot 25-7\cdot (-24)
$$
modulo 100 due to the Chinese Remainder Theorem. Finishing this calculation we get
$$
3\cdot 25-7\cdot(-24)=10\cdot 25-7=243
$$
to see that $7^{355}\equiv 243\equiv 43$ modulo 100.
Let $n=k^3.$ If $n$ has $6$ digits, the largest it could be is $(6\cdot 9)^3 = 157464$, which shows that one digit must be $1$. So in fact the largest it could be is $(1+5\cdot 9)^3 = 97336$ which is too small. So there are no $6$ digit (or larger) solutions. (I think this is the gist of @dezdichado's comment.)
Because the cube root of $100,000 = 46.4\ldots$, we know that $k\leq 46.$ Using your observation that $k\equiv -1, 0, 1 \pmod{9}$ leaves us with only these $16$ possibilities for $k$:
$$1, 8, 9, 10, 17, 18, 19, 26, 27, 28, 35, 36, 37, 44, 45, 46.$$
We can just check these or we can play a bit more:
Since $(5\cdot 9)^3 = 91125$, we see that a $5$-digit solution must have at least one non-$9$ digit. Since $(4\cdot 9+8)^3 = 85184$, the largest the first two digits can be is $79$, so at least one digit is at most $7$. Since $4\cdot 9 +7 = 43$ we can cross off the last three numbers from the list.
Of these, $1, 8, 17, 18, 26, 27$ work.
A couple of observations: It surprises me that the last two pairs are consecutive, and both are of the shape $-1, 0 \pmod{9}$ so I feel like I've missed something. Since $1$ is a solution, it doesn't seem like modular considerations would eliminate $1 \pmod{9}$.
Best Answer
$\phi(100)=40$, so we can reduce the exponent mod $40$: $$ 27^{2018}\equiv27^{18}\pmod{100} $$ Then we can square and multiply: $$ \begin{align} 27^2&\equiv29\\ 27^4&\equiv41\\ 27^8&\equiv81\\ 27^9&\equiv87\\ 27^{18}&\equiv69\pmod{100} \end{align} $$