I've developed a small bash script (I plan to rewrite it in Perl, maybe) which checks the status of the current Internet connection by pinging a certain number of hosts out of a list.
This really doesn't sound quite spectacular - and the prototype even was a 10-line code, but I've decided, that I didn't want to bug the "good guys" with high availability (google, etc...) and so I've taken the blacklist from our SquidGuard (proxy-filter) and enhanced my script to ping random hosts serving porn sites.
This has proven to be a VERY good indicator of the connection state and my script even stays on the secure side, by re-checking different hosts if a certain percentage of the previous round fails.
To avoid unnecessary load during the check itself, a standalone part of the script refines the blacklist and outputs a list of blank IPs and if desired, already pre-checks them (once, if asked to) for availability (to avoid un-pingable ones)
I'll provide a link to a small package with this program shortly.