We have already established that 9x9 sudoku is too easy for computers (hardest ones solved in milliseconds) -
Sudoku solution generator algorithm

An easy way to increase difficulty is to make the board bigger. Like 25x25.

This is one I found on a random website (of "extreme" difficulty). I transcribed it into this computer-parseable format -
Code:
0 0 12 6 0 0 7 0 18 0 5 24 0 10 1 0 0 4 0 0 0 0 0 0 0 
2 0 19 0 13 0 0 0 10 0 0 0 0 0 0 0 0 18 5 0 0 0 0 0 1 
0 0 0 0 0 0 0 22 0 0 0 0 3 0 2 0 0 14 12 0 16 8 25 0 0 
0 16 0 0 0 2 23 0 0 13 12 22 0 0 0 21 15 19 3 0 0 0 0 14 0 
23 0 24 0 0 0 0 0 25 8 4 0 16 19 21 0 0 7 0 0 0 3 12 0 9 
0 4 0 2 0 0 0 0 0 0 0 10 0 24 12 17 16 0 0 0 5 0 0 0 0 
0 0 9 0 0 6 25 0 0 0 8 0 5 3 0 0 0 0 0 0 20 0 0 18 19 
15 0 10 11 0 0 0 18 12 19 0 0 0 0 0 0 0 23 0 0 7 0 0 4 0 
0 0 0 0 0 0 0 14 0 22 0 0 18 16 20 0 6 11 13 0 0 0 0 0 0 
0 22 0 25 0 0 1 17 5 4 7 0 0 14 0 8 3 21 0 0 11 0 0 0 6 
0 20 13 15 0 0 0 0 0 0 9 0 0 2 0 25 0 1 8 0 0 5 0 21 0 
0 1 0 0 0 0 16 10 0 7 0 0 4 20 0 0 9 0 0 14 0 24 0 17 0 
25 2 5 0 0 0 0 0 13 0 0 0 0 0 22 0 0 0 0 0 19 1 8 0 0 
0 0 7 21 0 0 12 0 2 17 0 0 0 18 6 16 0 0 15 0 0 13 0 10 0 
8 10 18 12 16 9 0 0 0 5 0 0 0 0 19 0 0 17 0 21 0 15 0 0 22 
0 8 0 0 15 0 3 0 6 0 21 0 0 7 0 18 14 5 0 1 0 0 0 0 0 
0 0 0 19 0 1 0 16 11 0 0 0 10 22 25 15 0 0 0 0 0 0 21 0 0 
0 3 1 0 21 0 0 4 0 0 0 0 2 0 13 0 24 25 0 0 14 0 0 6 0 
0 0 0 0 0 0 0 15 0 12 14 0 6 17 24 0 0 0 0 0 0 0 13 0 0 
0 5 23 16 4 0 13 24 7 2 0 9 0 0 15 3 0 22 0 0 0 0 0 0 8 
0 0 25 20 2 0 19 0 0 0 0 1 0 0 0 0 21 3 0 0 12 0 0 0 0 
16 12 0 5 0 11 21 0 23 0 0 15 0 0 0 0 19 9 0 0 0 0 0 25 10 
0 0 0 0 9 20 22 7 4 0 3 0 14 25 18 0 11 0 0 0 0 0 1 0 15 
24 0 6 0 22 8 0 25 14 0 10 11 0 9 0 20 1 16 0 7 0 23 0 0 13 
14 13 21 1 0 0 5 0 0 0 6 0 22 0 23 10 0 0 0 2 0 0 18 7 11
0 means blank, filled in values are 1-25.

Or, in another format -
Code:
..LF..G.R.EX.JA..D.......
B.S.M...J........RE.....A
.......V....C.B..NL.PHY..
.P...BW..MLV...UOSC....N.
W.X.....YHD.PSU..G...CL.I
.D.B.......J.XLQP...E....
..I..FY...H.EC......T..RS
O.JK...RLS.......W..G..D.
.......N.V..RPT.FKM......
.V.Y..AQEDG..N.HCU..K...F
.TMO......I..B.Y.AH..E.U.
.A....PJ.G..DT..I..N.X.Q.
YBE.....M.....V.....SAH..
..GU..L.BQ...RFP..O..M.J.
HJRLPI...E....S..Q.U.O..V
.H..O.C.F.U..G.RNE.A.....
...S.A.PK...JVYO......U..
.CA.U..D....B.M.XY..N..F.
.......O.LN.FQX.......M..
.EWPD.MXGB.I..OC.V......H
..YTB.S....A....UC..L....
PL.E.KU.W..O....SI.....YJ
....ITVGD.C.NYR.K.....A.O
X.F.VH.YN.JK.I.TAP.G.W..M
NMUA..E...F.V.WJ...B..RGK
Me and my friend have double checked it, so it should be correct. The "numbers" version is generated from the "letters" version with a simple program.

I changed my "blazingly fast" 9x9 solution to work with 25x25 board, and, well, it has been running for half an hour now. No solution yet .

Anyone else want to take a stab at it?

It HAS to be possible, since the puzzle is meant to be solved by a human...

Bragging only in this thread, please (for now) , don't spoil it for me, yet.