“No suitable Destination Host found by cups-browsed”

I was able to get my printer working. This seems to be some sort of bug in cups-browsed, which is a program that tries to automatically install every printer on the network. After removing cups-browsed I was able to manually add the printer, and was able to print without rebooting before hand.

First: uninstall cups-browsed

sudo apt-get purge --autoremove cups-browsed

Next: Restart your computer

Finally manually add your printer

1. In Ubuntu 18.04 go to settings -> devices -> printers.
2. Click on 'Additional Printer Settings'.
3. Click on Add
4. Under Network Printers select Find Network Printer. Enter the IP Address that your server running CUPS has. Once you follow the steps to install your printer you should be able to print consistently without rebooting.

You dont need to remove anything or add your printer manually. Just do this:

systemctl stop cups-browsed

systemctl start cups-browsed

or simplifying:

systemctl restart cups-browsed

I did the full start and stop, and it worked for me.

I have a similar answer to @burnedfaceless that I came upon somewhat by accident. Since I was not comfortable removing a service that came with the system (Pop!_OS 20.04), I ran

systemctl stop cups-browsed

I then manually searched for and added the printer via Settings > Printers > Add...

At that point I was able to print normally, and only the one, manually-added, instance of my printer was visible. To test this further, I rebooted, expecting cups-browsed to restart itself (it did) and a second instance of the same printer to appear via the cups-browsed service (it did not, happily). So far so good. I am not sure why cups-browsed did not automatically add its own instance of the printer, but glad it did not.

One difference I have noted since doing this is that if I run:

lpstat -t
scheduler is running
system default destination: <short printer name>
device for <short printer name>: dnssd://<full url-encoded printer name>._ipp._tcp.local/?uuid=e...

If I recall correctly, the device URI was implicitclass://<printer name>, or something like that, when cups-browsed added it. Now it is dnssd://.... Perhaps this makes sense to someone who understands CUPS and/or systemd much better than I do.

Restart and even reinstall cups-browsed did not help me. Only solved this by assigning printer fixed IP address in the router settings and then added new printer manually with address ips://fixed-printer-ip-address/ips and selected proper driver.

This happened to me, too. I'd previously been able to print easily with mDNS (aka Avahi aka Bonjour), but recently found I couldn't print from my laptop -- even though I could SSH to the CUPS print server and print a test page just fine, could see the CUPS IPP service on port 631 (which you can just browse to in a web browser), and could even see the mDNS record being correctly broadcast. I couldn't get cups-browsed to resolve the hostname, when I ran cups-browsed -v in terminal I saw it looking at the mDNS broadcast data but also reporting:

Printer ipps://<model_name> @ ._ipps._tcp.local/cups (.local, IP not determined)

Eventually I realized I'd reconfigured /etc/nsswitch.conf, essentially bringing this upon myself. I had updated the hosts: line to put [!UNAVAIL=return] before the mdns4_minimal entry, meaning that systemd-resolved would try /etc/hosts and normal DNS, but quit before turning to mDNS. I moved [!UNAVAIL=return] after mdns4_minimal, restarted networking with sudo systemctl status networking.service, and then was able to see it getting resolved by mDNS correctly.

You can't use standard DNS tools to validate this, but you can use avahi-browse --all or avahi-discover to see what's being broadcast via mDNS, and then you can use ping <hostname>.local to test whether <hostname> is resolvable via mDNS.

I had similar issues. Right after a fresh install I could print just fine, as well as after updating, but eventually after personalizing my install, network printing would break. USB printing was never a problem. Turns out the issue was my VPN (Mullvad). Once I realized this and changed the setting in Mullvad to allow local devices, all is well.