I know that boost or compiler should be last to blame, but I can't see another explanation here. I'm using msvc 2008 SP1 and boost 1.43.

In the following code snippet execution never leaves third BOOST_FOREACH loop

typedef Graph<unsigned, unsigned>::VertexIterator Iter;

Graph<unsigned, unsigned> g;
g.createVertex(0x66);

// works fine
Iter it = g.getVertices().first, end = g.getVertices().second;
for(; it != end; ++it)
    ;

// fine
std::pair<Iter, Iter> p = g.getVertices();
BOOST_FOREACH(unsigned handle, p)
    ;

// fine
unsigned vertex_count = 0;
BOOST_FOREACH(unsigned handle, g.getVertices())
    vertex_count++;

// oops, infinite loop
vertex_count = 0;
BOOST_FOREACH(unsigned handle, g.getVertices()) 
    vertex_count++;

vertex_count = 0;
BOOST_FOREACH(unsigned handle, g.getVertices())
    vertex_count++;

// ... last block repeated 7 times

Iterator code:

class Iterator 
    : public boost::iterator_facade<Iterator, unsigned const, 
                boost::bidirectional_traversal_tag>
{
public:
    Iterator()
        : list(NULL), handle(INVALID_ELEMENT_HANDLE)
    {}

    explicit Iterator(const VectorElementsList &list, unsigned handle = INVALID_ELEMENT_HANDLE)
        : list(&list), handle(handle)
    {}

    friend std::ostream& 
    operator<<(std::ostream &s, const Iterator &it)
    {
        s << "[list: " << it.list <<", handle: " << it.handle << "]";
        return s;
    }

private:
    friend class boost::iterator_core_access;

    void increment()
    {
        handle = list->getNext(handle);
    }

    void decrement() 
    {
        handle = list->getPrev(handle);
    }

    unsigned const& dereference() const
    {
        return handle; 
    }

    bool equal(Iterator const& other) const
    {
        return handle == other.handle && list == other.list;
    }

    const VectorElementsList<T> *list;
    unsigned handle;
};

Some ASM fun:

    vertex_count = 0;
    BOOST_FOREACH(unsigned handle, g.getVertices())
// initialization
013E1369  mov         edi,dword ptr [___defaultmatherr+8 (13E5034h)] // end iterator handle: 0xFFFFFFFF
013E136F  mov         ebp,dword ptr [esp+0ACh] // begin iterator handle: 0x0
013E1376  lea         esi,[esp+0A8h] // begin iterator list pointer
013E137D  mov         ebx,esi 
013E137F  nop

// forever loop begin
013E1380  cmp         ebp,edi 
013E1382  jne         main+238h (13E1388h) 
013E1384  cmp         ebx,esi 
013E1386  je          main+244h (13E1394h) 
013E1388  lea         eax,[esp+18h] 
013E138C  push        eax
// here iterator is incremented in ram
013E138D  call        boost::iterator_facade<detail::VectorElementsList<Graph<unsigned int,unsigned int>::VertexWrapper>::Iterator,unsigned int const ,boost::bidirectional_traversal_tag,unsigned int const &,int>::operator++ (13E18E0h) 
013E1392  jmp         main+230h (13E1380h) 
        vertex_count++;
// forever loop end

It's easy to see that iterator handle is cached in EBP and it never gets incremented despite of a call to iterator operator++() function.
I've replaced Itarator implmentation with one deriving from std::iterator and the issue persisted, so this is not iterator_facade fault. This problem exists only on msvc 2008 SP1 x86 and amd64 release builds. Debug builds on msvc 2008 and debug/release builds on msvc 2010 and gcc 4.4 (linux) works fine. Furthermore the BOOST_FOREACH block must be repeaded exacly 10 times. If it's repeaded 9 times, it's all OK.

I guess that due to BOOST_FOREACH use of template trickery (const auto_any), compiler assumes that iterator handle is constant and never reads its real value again.

I would be very happy to hear that my code is wrong, correct it and move on with BOOST_FOREACH, which I'm very found of (as opposed to BOOST_FOREVER :).

May be related to: http://stackoverflow.com/questions/1275852/why-does-boost-foreach-not-work-sometimes-with-c-strings