Can you hide a server's existence on the internet?

You can set your server to normally drop all incoming packets and only open a port after it gets/sees a set of packets that specify a specific sequence of ports (this is called port knocking). I use this technique with my server; you cannot normally see the server because it drops all incoming packets. Once the port knocking packets reach the server, the server will then accept packets from the 'knocking' address but continue to drop packets from other addresses.

Security is better with this method because IP scans and attempted brutes won't be much of an issue to you. In order to hack a server there must be recon, to find out what services are running, what kind of OS you have, etc. By denying an attacker this info, it makes it harder for him to craft his attack for your device. The weakness of this defense is that if an attacker can see the incoming knocking packets, they can then open that port as well.

Would it possible to appear as though a server doesn't exist ... unless a specific phrase was provided in the request?

My guess is that you are talking about HTTP (i.e. "web") and a HTTP request here although you don't specify what kind of request you actually mean. In case of a HTTP request such hiding is not possible because HTTP is an application protocol on top of TCP. This means that the client first needs to establish a TCP connection which involves a reply from the server before the client will even send the application data (i.e. the HTTP request) and thus the existence of the HTTP server is revealed independent of the request.

This can be different with other protocols. For example DNS (resolving hostnames to IP address) is usually handled in UDP which is connectionless contrary to TCP. This means that the request with the payload is the first packet sent by the client. Thus a server could be created with UDP which only replies if the DNS request is for a specific domain and drop any other request. This way the server would reveal its existence only if the proper request was sent. Similar things could be done with SIP (telephony over internet) which is usually also done over UDP.

Is it possible to have all requests believe hostname could not be resolved ...?

Resolving a hostname to an IP address is done before even sending the request to the server on this IP address and usually the server itself is not even involved in this DNS resolving process. This means that even with connectionless protocols the client does not get the information that the name can not be resolved if the request was wrong. The most the client will get is the information that the target does not reply which might be interpreted that no server is setup on this IP address or that the server is down, protected by a firewall or simply dropping unexpected packets.

Would it possible to appear as though a server doesn't exist?

Yes, though this is non-trivial. It depends on the behavior of your ISP when a server does not exist. Some ISP configure their routers to drop packets when the IP a packet is trying to reach does not exist, others send a reject packets message back to the sender. Also, some routers have adaptive behavior, and change their behavior if it believes it may be under attack. Some ISPs may discriminate based on where the probing packets came from (e.g. packets coming from countries/ISPs that often hosts malicious customers may be treated more hostile than those with good network practices).

If you configure your server to simply drop all unrecognized packets, that may actually be evidence of the server's existence if your ISP normally sends a reject message. If your ISP's router adaptively change its behavior during a period of active attack, and your server don't keep up with what the ISP is doing, then that may be actually become evidence of the server. Additionally, your ISP may have their own backhaul ISP, which may have their own set of behavior.

Is it possible to have all requests believe host-name could not be resolved

Yes, just don't register your hostnames in the public DNS system. Hostnames in the public DNS system is intentionally public record. If it is registered in the public DNS, then anyone can query the DNS records to lookup the IP address related to the hostname. You can however, define hostnames that are only recognized by your machines (i.e. use hosts file) or run your own private DNS server.

Is there some evidence of a servers existence that could not be hidden by the owner of the server?

Any publicly routable IP address have public ownership record that can be queried using the whois tool to find out who your internet service provider is. Your ISP (or an adversary that compromises or works with your ISP) can monitor any packets going through their network and they can see that inbound packets without an earlier outbound packet as evidence of a server.

Would there be any practical added security?

If you have poor security practices in the first place, then being invisible may effectively turn away many simple-minded bots and unsophisticated attackers. More sophisticated attackers can find ways around invisibility. If you have good security practices, using strong authentication and encryption, then being hidden does not matter that much in terms of security.

Probably the best place to hide a leaf is to hide it in a tree/forest. If you run a publicly known server and you encrypt all traffic to the server (HTTPS only), then there is little that outsiders can do to distinguish between traffic to the front site and traffic to the hidden site. The only thing you need to consider is that TLS leaks the destination hostname in the SNI header. As long as you either spoof your SNI header or if you use the front server's hostname, then your hidden server would stay hidden.