I also have an 80GB iPod 5.5G and I'm having the exact same problem using database mode. It's extremely annoying having to wait so long to play music as it "searches" what apparently is already supposed to be saved. Before posting this I tested and it took between 3-4 minutes to begin playing all songs using database mode, and this is with dircache turned on and load to ram on (see settings below).
The tremendous battery drain while the disc is constantly spinning is also criminal, and makes me recall an old quote someone made some time back on the iaudiophile forums - "Rockbox rapes my battery."
Here's my config file as well - I'm smelling a problem here and really hope someone can help...
# .cfg file created by rockbox r13492M-070525 -
http://www.rockbox.orgvolume: -13
balance: 0
bass: -6
treble: 0
channels: stereo
stereo_width: 100
shuffle: on
repeat: all
backlight timeout: 10
backlight timeout plugged: on
invert: off
flip display: off
invert cursor: on
statusbar: on
scrollbar: off
volume display: graphic
battery display: graphic
time format: 24hour
show icons: off
idle poweroff: 10
max files in playlist: 8000
max files in dir: 350
battery capacity: 400
car adapter mode: off
userfont1: /.rockbox/fonts/helvR10.fnt
userfont2: /.rockbox/fonts/helvR12.fnt
userfont3: /.rockbox/fonts/helvR14.fnt
userfont4: /.rockbox/fonts/helvR18.fnt
backlight filters first keypress: off
caption backlight: off
backlight fade in: off
backlight fade out: 500ms
scroll speed: 9
scroll delay: 1000
bidir limit: 50
Screen Scrolls Out Of View: off
scroll step: 6
screen scroll step: 16
scroll paginated: off
foreground color: FFFFFF
background color: 000000
play selected: on
party mode: off
volume fade: on
scan min step: 1
scan accel: 3
antiskip: 5s
disk spindown: 3
show files: all
sort case: off
follow playlist: off
playlist viewer icons: on
playlist viewer indices: on
playlist viewer track display: track name
recursive directory insert: off
autocreate bookmarks: off
autoload bookmarks: off
use most-recent-bookmarks: off
peak meter clip hold: 60
peak meter hold: 500ms
peak meter release: 8
peak meter dbfs: on
peak meter min: 60
peak meter max: 0
talk dir: off
talk file: off
talk menu: on
sort files: alpha
sort dirs: alpha
id3 tag priority: v2-v1
ipod scroll wheel fast threshold in clicks/sec: 135
ipod scroll wheel faster threshold in clicks/sec: 235
ipod scroll wheel fastest threshold in clicks/sec: 400
rec timesplit: off
rec sizesplit: off
rec channels: stereo
rec split type: Split
rec split method: Time
rec source: mic
prerecording time: 0
rec directory: /recordings
cliplight: off
cliplight: off
rec mic gain: 16
rec left gain: 0
rec right gain: 0
rec frequency: 44
rec format: wave
mp3_enc bitrate: 128
trigger start threshold: -35
trigger stop threshold: -45
trigger start duration: 0s
trigger stop postrec: 2s
trigger min gap: 1s
trigger mode: off
folder navigation: off
gather runtime data: off
replaygain: off
replaygain type: album
replaygain noclip: off
replaygain preamp: 0
beep: off
crossfade: off
crossfade fade in delay: 0
crossfade fade out delay: 0
crossfade fade in duration: 0
crossfade fade out duration: 0
crossfade fade out mode: crossfade
crossfeed: off
crossfeed direct gain: 15
crossfeed cross gain: 60
crossfeed hf attenuation: 160
crossfeed hf cutoff: 700
eq enabled: on
eq precut: 50
eq band 0 cutoff: 150
eq band 1 cutoff: 392
eq band 2 cutoff: 807
eq band 3 cutoff: 4002
eq band 4 cutoff: 12000
eq band 0 q: 9
eq band 1 q: 12
eq band 2 q: 12
eq band 3 q: 12
eq band 4 q: 9
eq band 0 gain: 40
eq band 1 gain: -110
eq band 2 gain: -110
eq band 3 gain: -120
eq band 4 gain: 0
dithering enabled: off
dircache: on
tagcache_ram: on
click insert setting: original
tagcache_autoupdate: on
default codepage: iso8859-1
warn when erasing dynamic playlist: off
backlight on button hold: normal
eq hardware enabled: on
eq hardware band 0 cutoff: 105Hz
eq hardware band 0 gain: 0
eq hardware band 1 center: 300Hz
eq hardware band 1 bandwidth: narrow
eq hardware band 1 gain: 0
eq hardware band 2 center: 850Hz
eq hardware band 2 bandwidth: narrow
eq hardware band 2 gain: 0
eq hardware band 3 center: 2.4kHz
eq hardware band 3 bandwidth: narrow
eq hardware band 3 gain: 0
eq hardware band 4 cutoff: 6.9kHz
eq hardware band 4 gain: 0
hold_lr_for_scroll_in_list: on
show path in browser: off
pause on headphone unplug: off
rewind duration on pause: 0
disable autoresume if phones not present: off
Last.fm Logging: off
trigger type: stop
backlight timeout plugin: on
font: /.rockbox/fonts/helvR12.fnt
browserfont: /.rockbox/fonts/helvR12.fnt
wpsfont: /.rockbox/fonts/helvR10.fnt
menufont: /.rockbox/fonts/helvR12.fnt
wps: /.rockbox/wps/Flow.wps
backdrop: /.rockbox/backdrops/Flow.bmp
usb charging: on
cuesheet support: off
listxpos: 5
listypos: 38
listlines: 13
listwidth: 302
start in screen: wps
alarm wakeup screen: wps
iconset: /.rockbox/icons/elisherer.12x13.bmp
viewers iconset: /.rockbox/icons/elisherer.12x13_viewers.bmp