Does a 15-puzzle always have a solution

Martin Gardner had a very good writeup on the 14-15 puzzle in one of his Mathematical Games books.

Sam Loyd invented the puzzle. He periodically posted rewards for solutions to certain starting configurations. None of those rewards were claimed.

Much analysis was expended, and it was finally determined, through a parity argument (as mentioned in the comment above), that half of the possible starting configurations were unsolvable. Interestingly, ALL of Loyd's reward configurations were unsolvable.

SO: No, every possible configuration is not solvable. If you START with a solved puzzle, and apply only legal transformations (moves) to it, you always wind up at a solvable configuration.

For the GENERAL nxm question, you'd probably have to expand the parity argument.

Just a hint. Once I had to show with basic algebra (permutation groups) that a standard $15$ puzzle had no solution. The idea there was the following:

to rearrange the puzzle, you have to perform a permutation of the $15$ tiles.

Now, notice that once you write any permutation allowed, it is written as a product of an even number of $2$-cycles (you always move the "empty" tile, it starts in the corner and it has to be still there at the end of your moves). Hence permutation with sign $-1$ are not allowed.

In my case it was enough to conclude the puzzle had no solution (I had to perform an exchange between two tiles, so it had sign $-1$). Maybe it can help you to exclude some configurations.