One place where magnetic sensing is very useful is in dirty applications. If the area you're getting the reading from is at all exposed to the elements, then magnetic definitely is the way to go. This is probably the case for your application, and high RPM is definitely not a factor.
For sensing wheel rpm on my dirt bikes I use little neodymium button magnets. They produce amazingly dense fields and certainly work well with a hall effect devices, even at a fair distance. I get them at trailtech.net/magnets.html, but they are probably available on ebay for less.