Thank you, Google. We could have never spelled "Arnold Schwarzenegger" without you.
This means we either learned to spell the name and didn't have to consult Google anymore, or only had to spell it once.
Thank you, Google. We could never spell "Arnold Schwarzenegger" without you.
This is implying every time we need to spell the name, we are needing to consult Google.
The construct "we could have never X without Y" is commonly used when thanking people for helping them with some trouble or challenge in the past. The first thing that comes to my mind when hearing this is someone accepting an award at an awards ceremony. So if the writer desired to communicate thankfulness, this is another reason why they worded it this way.