First made my account in 2004, came back and all my characters are missing. I used to be able to look them up in wowarmory but that no longer works either.
Some missing character details:
Ragu - gnome mage - Mannoroth
Fasolt - night elf hunter - Kael’thas
Sekhet - night elf druid - Kael’thas
Tried working with support but apparently they couldn’t find them either and are asking for the original product key from 04.
Have you tried making new toons to refresh the realms? There have been times when the levels been redused and name released.
The armory can drop characters if not logged in for a while. So is not a great means to locate characters. Especially because names are released to be used again by more active players.
Makes me think it is on a different account, and the billing staff are trying to establish if you are the actual owner of that account.
I’m afraid the WoW license on this Battlenet account is not from 2004, it was created in 2013.
While the name release system no longer works like this, it used to be that when a name became eligible to be released they would automatically be flagged for a rename and be given some random numbers/letters at the end. So that would turn a name like Vrakthris into something like Vrakt5DF2. A little difficult to find, but not terrible. Include a class and race it makes it much easier.
Your character names are fairly short, so odds are our Support staff had more than a little bit of trouble hunting for them.
I got a little bit luckier. 
It appears you have the Bnet account name close, but instead of @gmail you should be logging into @Live.
The account looks to be locked, but that might be able to be resolved by just resetting your password.
You have a bunch of characters on several realms but once you regain access I think the main ones you want to check are Blackrock, Burning Blade, Kael’thas, Mannoroth, and Thunderlord.