I took out the battery, put some water on my fingers and gently ran them over the phone keys (sounds sexual, eh ...). They losened up for the next 5 or so hours before getting sticky again - but no where near to the extent that they were.
I've done 3 times since, so perhaps I'll doing this every day and see what hapens - and hope I don't need a new phone :/