The theory behind undelete programs is that deleting a file doesn't really delete the data; as such, it's better to call it unlinking. If the old space hasn't been reallocated for use by a new file, then all a program needs to do is scan the unallocated portions for structures that represent files and relink them to the existing file system.
So to answer your question, in theory it doesn't matter what medium is used to store the data; unless the program is badly written, it should be able to recover files if they haven't been overwritten.