Those were the solutions I got. And they ARE the only solutions.
I have proved it using funny diagrams and logic, but I can't draw these diagrams and show my proof formally on this site.
The basic idea of the proof (don't read if you want the complete challenge for yourself):
First you need to prove that all solutions involve a 5 digit number and a 4 digit number. This is easy.
Then you prove that the 5 digit number starts in either 3 or 4. (easy)
Then you assume that the first number is 3, then show that there is no possible solutions with the first digit being 3. This is slightly longer, but still easy.
Then I drew a table of all the possible pairs of number that their difference is 3 or 4, and grouped them into four groups:
(4,X). remainder four, the first number in the pair is the larger one. i.e. (9 - 5)
(4,Y). remainder four, the first number is smaller. i.e. (3 - 9)
(3,X). remainder three, first is larger. i.e. (9 - 6)
(3,Y). remainder three, first is smaller. i.e. (2 - 9)
You need to pick four pairs that do not repeat a digit and do not include zero or 4 (because this is the first digit of the 5 digit number).
http://i349.photobucket.com/albums/q390/Georgepowell77/DSC00137.jpg
That is an image of my basic idea.
There are now 8 situations that could lead to a solution. I went through each one and proved that 7 of them could not yeild a solution (I did this by using weird clock-like diagrams).
Then there is one combination of group choices that could lead to a solution. and it is very easy to show that there are only two combinations of pairs from these groups that leads to a solution. And they are the solutions that we got.