I use all relative links and have never had any problems. Granted I don't have any absolute vs relative data but the fact remains that I have yet to see pages not indexed because of it. They all seem to get in eventually (except for INK of course ;))
No evidence that spiders follow abs better than relative. However, there is evidence that absolute has enough qualities that make them very attractive. From an issue of the quarterly on Absolute vs Relative [searchengineworld.com] from last year.