I finally got it working with almost any kind of tile. And since the algorithm is just used to generate configuration files for another application, I'll fix the remaining tiles manually :)
Here is my solution for anyone interested:
Raise the contrast and lower the brightness of the image in order to easily distinguish the walls from the rest:
Divide each tile on a 6x6 grid of 200x200px squares. For each square, compute the average RGB value for each side on a 30px side line.
Compare this value to the rest of the tile. If the difference is greater than a specific delta (found empirically), then it's a wall.
Go around each tile on the border to check for walls leading to the exit (vertical walls for the top side, etc) and once you identified them, finding which tile leads to the exit is rather trivial.
Here is the final result on various tiles: