The second graph you showed is annotated with \$I_D=31A\$, which is well beyond your own requirement, and only represents behaviour along that line on the \$I_D\$ vs. \$V_{DS}\$:
![enter image description here](https://cdn.statically.io/img/i.sstatic.net/CwsgCurk.png)
The graph of \$R_{DS(ON)}\$ isn't very useful here, except in the sense that it does suggest that the device is expected to be used in applications demanding far greater drain current than you will be using.
at 3.0v V(gs) and 12v (Vds) it should be able to flow over 3 amps
You have forgotten than when the transistor is on, you require it to have almost no voltage across it, \$V_{DS} \approx 0V\$:
![schematic](https://cdn.statically.io/img/i.sstatic.net/UbuNrPED.png)
simulate this circuit – Schematic created using CircuitLab
The relay coil should have all 12V, and therefore, that 12V, 3A point is irrelevant for your calculations.
Rather, you will be operating the device near the left edge of the graph of \$I_D\$ vs. \$V_{DS}\$, near \$V_{DS}=0.1V\$, for which the appropriate line (bottom) shows \$I_D \approx 1A\$.
I seriously doubt that anything strange happens further to the left than shown on that graph, and I would expect this MOSFET to maintain low enough \$R_{DS}\$ that \$V_{DS}\$ remains below 0.1V for all currents below 1A. For this reason, I too would expect this device to work in your application.
Despite that belief, I wouldn't recommend making such extrapolations. That the graph doesn't include conditions under which you intend to operate is an indication that this device probably isn't right for you.
I remind you also that the quoted worst-case \$V_{GS(TH)}=2.35V\$ is valid only for \$I_D=25\mu A\$, and for \$V_{DS}\$ significantly greater than zero, so this value is not a good indicator of what gate potential will pass hundreds of milliamps of drain current.
Still, why doesn't it work? I think it should. Perhaps it's damaged, which is easy enough to do with imprudent handling. The gate isn't protected against ESD like most CMOS integrated circuit inputs, so if you don't take care to avoid ESD, then you could easily blast a hole in the gate before you even switch the circuit on.
Or, perhaps you got yourself a counterfeit device.
Aside from buying another one (from a reputable source), I would recommend testing the device in some kind of test rig, to obtain your own graphs, and see how they agree or differ from the datasheet's claims. That's what I would do.