Old thread, but in case someone finds this still relevant, I did finally discover the problem and solution.

If you Google memtoleave you will find the answer: SQL 2005 sets aside a separate address space apart from the buffer pool, used for things like OPENROWSET queries. If this becomes fragmented, you will be limited to using the largest contiguous chunk of memory left in it. The only way I'm aware of to reset this separate address space to the unfragmented value is to restart the SQL service, which is why bouncing the service "fixed" the problem.

The solution was to alter the service startup switch that allocates memtoleave memory to a larger value:

http://www.johnsansom.com/sql-server-memory-configuration-determining-memtoleave-settings/[/url]

http://sqlblog.com/blogs/jonathan_kehayias/archive/2009/07/07/understanding-the-vas-reservation-aka-memtoleave-in-sql-server.aspx

For SQL 2005, the relevant explanation is here, look for the "-g" startup switch, and increase it as needed. This robs RAM from the buffer pool, so be careful with it.

The article on Kehayias' link, above, includes a query you can run to determine how much VAS is left available, and the largest contiguous chunk left. I put a version of this query on an Agent job and ran it hourly, dumping the results to a logging table, so I could track the pool's depletion.

I think 2008 fixed this, but in case anyone still runs 2005 I figured I'd post this fix.

Rich