The file <filename> is not an Outlook data file (.pst)

I know many people have seen this error when trying to add a .pst file in Outlook. I am having this problem now. I've done research and practically every site and forum I've been to says to use scanpst.exe. Well, here's the problem: when I use this .pst file in scanpst.exe, it pops up the below error:

"The Microsoft Outlook Inbox Repair Tool does not recognize the file <filename>. No Information can be recovered."

This is a backup of an original .pst file that got lost when the user's computer was re-imaged. I know you can add .pst backups into Outlook because I've done it. And I can also add a different .pst file in Outlook from the same exact folder.

I've also tried adding it in Outlook 2010 and I've tried adding it an Outlook 2013, both popped up the same error.

Does anybody have a fix or have any suggestions? I'm out of ideas.
 
I don't have any PSTs left so I can't demo this but

the first 4 bytes are unique (a pst value is different that a pdf value) and this is how Linux reacts to files, not by the filename.extension.

Now the tricky part - - perhaps you can get a HEXEDIT program to look at the file and you can see what's there. At least you would have some clue if it's an outlook file or pure trash.
 
Follow-up: Some notable values:
Code:
PDF:                                %PDF-1.5%âãÏÓ
openoffice::text                     PK
openoffice::spreadsheet:  ÐÏࡱá 
jpg::                                 ÿØÿî
gif::                                  GIF89a.
png::                                ‰PNG
these were seen using Open With --> \windows\notepad.exe which will open anything
 
Back