Upon taking up Jakes challenge to find the scanned versions of Sam and Max: surfing the highway, I happed to come across this (
http://www.sequentialtart.com/archive/june01/hastings_2.shtml) article.
Most of it is about Jon "Bean" Hastings comics, but there is a section about a third of the way down which reads:
ST: Which comics do you find funny?
JH: The Tick (my all-time favorite comic book), anything by Phil Foglio (pick up his new mad-science-themed book, Girl Genius. Do it! Now!), Bone, Evan Dorkin's stuff, Sam and Max: Freelance Police (look for a pinup by Steve Purcell in the first issue of Mad Science!)
Since I cannot deduce how old this article is (and because I have never heard of this comic) can a reliable source confirm if it is true that Steve did a piece for this comic book.