Don't do "service networking restart"; that's not a reliable way of down-upping all interfaces.
The "resolvconf -u" command only updates resolv.conf from resolvconf's own database. You need to update the database.
To update the database you have to call resolvconf with the -a or -d option. That happens behind the scenes when you run ifup or ifdown. So, normally, as with any other change to /etc/network/interfaces, to activate changes to the dns-* options you have to ifdown the interface in question and ifup it again. Or you can reboot.
If you want to make changes to an interface without ifdownupping it (perhaps because you are administering the machine remotely and happen to be connected via that interface, natch) then you can achieve the same result by running resolvconf directly from the command line. This requires a bit more knowledge of resolvconf's semantics. Assume the relevant /e/n/i stanza is
iface IIII FFFF static
address ...
...
dns-nameservers X.X.X.X Y.Y.Y.Y
dns-search SSSS
where FFFF is an address family ("inet" or "inet6").
To activate these dns-* options you run resolvconf as follows (yes, with newlines in the string piped to resolvconf).
echo "nameserver X.X.X.X
nameserver Y.Y.Y.Y
search SSSS" | sudo resolvconf -a IIII.FFFF
For the stanza given in the question this would be the following.
echo "nameserver 192.168.3.45
nameserver 192.168.8.10
search example.com" | sudo resolvconf -a eth0.inet
Consult the resolvconf(8) manual page and the resolvconf package README file (/usr/share/doc/resolvconf/README.gz) for more information.