Foobar2000 Faq:
QUOTE
Why is MP3 seeking so terribly slow?
The MP3 format doesn't natively support sample-accurate seeking, and sample accurate seeking is absolutely required by some other features of foobar2000 (such as .CUE playback). Therefore, MP3 seeking works by bruteforce-walking the MPEG stream chain (this gets faster when you pass through the same point of file for the second time because seektables have been built in the RAM). Unfortunately, seeking can't be optimized for CBR files (frame sizes aren't really constant because of padding used), or for VBR headers (both Xing and VBRI headers contain only approximated info and are useless for sample-exact seeking).