Minimal pairs are the thorough proof of phonemic status in an ideal world, but really they are hard to find quite often. The example of تين and طين does differ in the pronunciation of the ي, as the ii vowel is more centralized under the influence of the emphatic consonant. If it still sounds the same to anyone, I recommend recording it and actually looking at the waveform and the formants, especially at the beginning of the vowel. In fact, other than the back vowel /u/, I would assume it is always difficult to find minimal pairs with emphatic consonants simply because emphatic consonants in Arabic have that special ability to affect the sounds around them.
Fortunately, we don't have to rely on minimal pairs. If you have the sounds [d] and [D] in the same phonetic distribution, and if they are also different sounds, then they are phonemes of a language, /d/ and /D/. ض can occur anywhere in a word, د can also occur anywhere in a word. ض and د are different sounds. They are not in complementary distribution and are therefore phonemes. If only ض and never د occurred at the beginning of a word, and د and never ض occurred in all other positions, then that might be suspicious of being the same phoneme, although that is still harder to prove. It's rather easy then to show all these sounds are separate phonemes. It's not as strict as the minimal pair proof, but I think often just as effective.
A pair of sounds however, such as [æ] and [a] do not constitute separate phonemes because they occur under different phonological contexts [Ta: and not *Tæ: for example), and can therefore be considered to be different realizations of one vowel phoneme /a/.
I think the Arabic script does a pretty good job of having a 1 character: 1 phoneme transcription, at least when it comes to fus7a.
