I finally found a solution by using the "full file buffering" option in the advanced preferences (I set it a 150 MB since I have 2GB of RAM). Everything looked and sounded perfect with instantaneous seeking until I found what I think are two bugs:
1. Mp3 files larger than ~65MB don't load at all anymore.
2. Mp3 files loaded by a cue file are apparently NOT buffered (seek times still >1min and files >65MB still load).
PS: It would also be nice to be able to buffer all the MP3 files when loading a m3u.